library_for_python

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Kazun1998/library_for_python

:warning: Circle
(Geometric/Circle.py)

Theory

円の定義

点 $\mathrm{P}$ と正の実数 $r$ に対して, 点 $\mathrm{P}$ からの距離が $r$ であるような座標平面の部分集合を円という. つまり, この円を $\mathrm{C}$ とすると,

\[\mathrm{C}:=\{\mathrm{X} \in \mathbb{R}^2 \mid \operatorname{dist}(\mathrm{P}, \mathrm{X})=r \}\]

である. このとき, $\mathrm{P}$ を円 $\mathrm{C}$ の中心, $r$ を $\mathrm{C}$ の半径という.

2 円の位置関係

$\mathrm{C}$ は中心 $\mathrm{P}$ , 半径 $r$ の円, $\mathrm{D}$ は中心 $\mathrm{Q}$ , 半径 $s$ の円とする.

このとき, 2 円 $\mathrm{C}, \mathrm{D}$ の関係は以下 5 種類の場合分け出来る. なお, $d:=\operatorname{dist}(\mathrm{P}, \mathrm{Q})$ とする.

関係 条件 共通接線の数
一方が他方の外部にある $d \gt r+s$ 4 本
外接している $d=r+s$ 3 本
交わっている $\lvert r-s \rvert \lt d \lt r+s$ 2 本
内接している $d=\lvert r-s \rvert$ 1 本
一方が他方を含んでいる $d \lt \lvert r-s \rvert$ 0 本

直線と円の位置関係

$\mathrm{C}$ は中心 $\mathrm{P}$, 半径 $r$ の円とし, $\ell$ は直線とする. このとき, $\mathrm{C}$ と $\ell$ の関係は次のようにして 3 種類に分けられる. なお, $\mathrm{P}$ と $\ell$ との距離を $d$ とする.

関係 条件
共有点なし $d \gt r$
接している $d=r$
交わっている $d \lt r$

直線と円の交差判定

$\mathrm{C}$ は中心 $\mathrm{P}$, 半径 $r$ の円とし, $\ell$ は直線とする. また, $\mathrm{C}$ と $\ell$ は共有点を持つとする.

共有点を $\mathrm{X}, \mathrm{X}’$ (接する場合は $\mathrm{X}=\mathrm{X}’$ とする) とする.

このとき, $\mathrm{P}$ の $\ell$ への射影を $\mathrm{H}$ とすると, $\mathrm{X}, \mathrm{X}’$ は直線 $\mathrm{PH}$ に関して線対称である.

直角三角形 $\mathrm{PHX}$ に関する三平方の定理より

\[\mathrm{PX}^2=\mathrm{PH}^2+\mathrm{XH}^2\]

である. $\mathrm{X}$ は円 $\mathrm{C}$ 上の点であるから, $\mathrm{PX}=r$ である. よって,

\[\mathrm{XH}=\sqrt{\mathrm{PX}^2-\mathrm{PH}^2}=\sqrt{r^2-\mathrm{PH}^2}=:x\]

となる.

よって, $\ell$ の単位方向ベクトルを $\boldsymbol{e}$ とおくと,

\[\overrightarrow{\mathrm{OX}}=\overrightarrow{\mathrm{OH}}+\overrightarrow{\mathrm{HX}}=\overrightarrow{\mathrm{OH}}+x \boldsymbol{e}\]

である.

そして, $\mathrm{X}’$ は直線 $\mathrm{PH}$ に関して $\mathrm{X}$ と線対称であったから,

\[\overrightarrow{\mathrm{OX}'}=\overrightarrow{\mathrm{OH}}-x \boldsymbol{e}\]

である.

以上から, 交点は

\[\overrightarrow{\mathrm{OH}} \pm x \boldsymbol{e}\]

であるとわかった.

直線と円の交点

2 円の交差判定

2 円の位置関係における交わっているのみが交差している.

共有点判定の場合, 必要十分条件は $\lvert r-s \rvert \leq d \leq r+s$ になる.

2円の交点

$\mathrm{C}$ は中心 $\mathrm{P}$, 半径 $r$ の円, $\mathrm{D}$ は中心 $\mathrm{Q}$, 半径 $s$ の円とし, この 2 円は共通点を持つとする.

2 つの交点を $\mathrm{X}, \mathrm{X}’$ とする (内接, 外接の場合は $\mathrm{X}=\mathrm{X}’$ とする).

このとき, $\mathrm{X}, \mathrm{X}’$ は線分 $\mathrm{PQ}$ に関して線対称な位置にある. よって, $\mathrm{X}$ を求められれば十分である.

$\operatorname{dist}(\mathrm{P}, \mathrm{X})=r, \operatorname{dist}(\mathrm{Q}, \mathrm{X})=s$ である. また, $\mathrm{X}$ の線分 $\mathrm{PQ}$ への射影を $\mathrm{H}$ とし, $\theta:=\angle \mathrm{XPH}$ とすると,

直角三角形 $\mathrm{PXH}$ を考えることにより,

\[\mathrm{PH}=\mathrm{PX} \cos \theta=r \cos \theta =:x\]

である. そして, 三角形 $\mathrm{PQX}$ における第 II 余弦定理から

\[\cos \theta=\dfrac{r^2+d^2-s^2}{2dr}\]

である. よって, 直角三角形 $\mathrm{PXH}$　三平方の定理から

\[\mathrm{HX}=\sqrt{\mathrm{PX}^2-\mathrm{PH}^2}=\sqrt{r^2-\mathrm{PH}^2} =:y\]

である.

よって, $\overrightarrow{\mathrm{PQ}}$ の単位ベクトルを $\boldsymbol{e}$ , 単位法線ベクトルを $\boldsymbol{n}$ とすると,

\[\overrightarrow{\mathrm{OX}}=\overrightarrow{\mathrm{OP}}+\overrightarrow{\mathrm{PH}}+\overrightarrow{\mathrm{HX}}=\overrightarrow{\mathrm{OP}}+x \boldsymbol{e}+y \boldsymbol{n}\]

である. また, $\mathrm{X}’$ は線分 $\mathrm{PQ}$ に関して $\mathrm{X}$ の線対称な位置にあり, $\boldsymbol{n}$ は $\boldsymbol{e}$ の単位法線ベクトルであったので,

\[\overrightarrow{\mathrm{OX}'}=\overrightarrow{\mathrm{OP}}+x \boldsymbol{e}-y \boldsymbol{n}\]

である.

以上から, 交点は

\[\overrightarrow{\mathrm{OP}}+x \boldsymbol{e} \pm y \boldsymbol{n}\]

であることがわかった.

円の接線 (円上の点)

$\mathrm{C}$ は $\mathrm{P}$ を中心とする円であるとする. 円 $\mathrm{C}$ 上の点 $\mathrm{A}$ を通る円 $\mathrm{C}$ の接線 $\ell$ は次のようにして求められる.

$\mathrm{A} \in \ell$ であることが確定しているので, $\ell$ 上の点をもう一つ求められれば良い.

$\boldsymbol{v}:=\overrightarrow{\mathrm{PA}}$ とし, $\boldsymbol{v}’$ を $\boldsymbol{v}$ の法線ベクトルとすると, $\mathrm{B}:=\mathrm{A}+\boldsymbol{v}’$ において, $\mathrm{B} \in \ell$ である.

よって, $\ell$ は $\mathrm{A}, \mathrm{B}$ を通る直線である.

円の接線 (円外の点)

$\mathrm{C}$ は $\mathrm{P}$ を中心とする半径 $r$ の円であるとする. 円 $\mathrm{C}$ の外にある点 $\mathrm{A}$ を通る円 $\mathrm{C}$ の接線を求める.

$d:=\operatorname{dist}(\mathrm{P}, \mathrm{A})$ とする. 円 $\mathrm{C}$ の接点を $\mathrm{X}, \mathrm{X}’$ とする. この $\mathrm{X}, \mathrm{X}’$ は直線 $\mathrm{AP}$ に関して線対称の関係にある.

$\mathrm{X}, \mathrm{A}$ は円 $\mathrm{C}$ 上の接線で, $\mathrm{X}$ が接点になるので, $\angle \mathrm{PXA}=90^\circ$ である. よって, 直角三角形 $\mathrm{PXA}$ における三平方の定理により,

\[\mathrm{PA}^2=\mathrm{PX}^2+\mathrm{AX}^2\]

であるから, $d:=\operatorname{dist}(\mathrm{P}, \mathrm{A})$ 及び, $\mathrm{X}$ は $\mathrm{C}$ 上の点だったので,

\[\mathrm{AX}=\sqrt{\mathrm{PA}^2-\mathrm{PX}^2}=\sqrt{d^2-r^2}:=x\]

である. また, $\theta:=\angle \mathrm{PAX}$ とすると,

\[\theta=\operatorname{Sin}^{-1} \dfrac{\mathrm{PX}}{\mathrm{PA}}=\operatorname{Sin}^{-1} \dfrac{r}{d}\]

である.

従って, $\overrightarrow{\mathrm{AP}}$ の単位ベクトルを $\boldsymbol{e}$ とし, $\boldsymbol{e}$ を $\alpha$ だけ回転させたベクトルを $\boldsymbol{e}_\alpha$ とすると,

\[\overrightarrow{\mathrm{OX}}=\overrightarrow{\mathrm{OA}}+\overrightarrow{\mathrm{AX}}=\overrightarrow{\mathrm{OA}}+x\boldsymbol{e}_{\theta}\]

である. これにより, 接線の一つとして $\mathrm{A}, \mathrm{X}$ を通る直線となる.

また, $\mathrm{X}’$ は直線 $\mathrm{AP}$ に関して $\mathrm{X}$ と線対称の位置であるから,

\[\overrightarrow{\mathrm{OX}'}=\overrightarrow{\mathrm{OA}}+x\boldsymbol{e}_{-\theta}\]

である.

Code

from Point import *
from Line import *
from Affine import *

class Circle:
    __slots__ = ("center", "radius")

    def __init__(self, center: Point, radius: float):
        """ 点 center を中心とする半径 radius の円を生成する.

        Args:
            center (Point): 中心
            radius (float): 半径
        """
        assert radius >= 0

        self.center = center
        self.radius = radius

    def __str__(self) -> str:
        return f"[Circle] center: {self.center}, radius: {self.radius}"

    def __repr__(self) -> str:
        return f"{self.__class__.__name__}(center = {repr(self.center)}, radius = {repr(self.radius)})"

    def __contains__(self, Point):
        return equal(abs(Point - self.center), self.radius)

#=== 交差判定
def has_Intersection_between_Circle_and_Segment(C,L,endpoint=True):
    """円 C と線分 L の交差判定を行う.

    """

    c = C.center
    flag1 = compare(Distance_between_Point_and_Segment(c, L), C.radius) <= 0
    flag2 = compare(max(abs(c - L.begin), abs(c - L.end)), C.radius) >=0
    return flag1 and flag2

def has_Intersection_between_Circle_and_Line(C,L):
    """円 C と直線 L の交差判定を行う.

    """
    return compare(Distance_between_Point_and_Line(C.center,L), C.radius) <= 0

def has_Intersection_between_Circle_and_Circle(C,D):
    """2つの円 C,D の交差判定を行う.

    """

    r=C.radius; s=D.radius;
    d=abs(C.center-D.center)

    return compare(d, abs(r - s)) >= 0 and compare(d, r + s) <= 0

#=== 交点を求める
def Intersection_between_Circle_and_Line(C,L):
    """ 円 C と直線 L の交点を求める.

    """

    if not has_Intersection_between_Circle_and_Line(C,L):
        return []

    H=Projection(C.Center,L)
    d=Distance_between_Point_and_Line(C.Center,L)
    x=sqrt(max(C.radius*C.radius-d*d,0))
    v=L.vectorize(); v.normalization()

    return [H+x*v,H-x*v]

def Intersection_between_Circle_and_Circle(C,D):
    """ 2つの円 C,D の交点を求める.

    """

    if not has_Intersection_between_Circle_and_Circle(C,D):
        return []

    r=C.radius; s=D.radius

    v=D.center-C.center
    d=abs(v)
    v.normalization()
    w=v*Point(0,1)

    x=(d*d+r*r-s*s)/(2*d)
    y=sqrt(max(r*r-x*x,0))
    return [C.center+x*v+y*w,C.center+x*v-y*w]

#=== 接線
def Tangent_to_Circle_on_Point(P,C):
    """ 円 C 上の点 P を接点とする接線を求める.

    """

    assert P in C
    v=(P-C.center)*Point(0,1)

    return Line(P,P+v)

def Tangent_to_Circle_from_Point(P,C):
    """ 点 P から引く円 C への接線を求める."""

    v=C.center-P
    d=abs(v); v.normalization()
    r=C.radius

    x=sqrt(max(d*d-r*r,0))
    theta=asin(r/d)

    return [Line(P,P+x*v.rotate(theta)),Line(P,P+x*v.rotate(-theta))]

def Common_Tangent_between_Circle_and_Circle(C,D):
    """ 円 C,D の共通接線を求める."""

    r=C.radius; s=D.radius
    d=abs(C.center-D.center)

    X=[]

    K=Circle(Point(),r)
    if compare(d,abs(r-s))>=0:
        a=r*(r-s)/d
        b=sqrt(max(0,r*r-a*a))

        X.append(Tangent_to_Circle_on_Point(Point(a,b),K))
        X.append(Tangent_to_Circle_on_Point(Point(a,-b),K))
    if compare(d,abs(r+s))>=0:
        a=r*(r+s)/d
        b=sqrt(max(0,r*r-a*a))

        X.append(Tangent_to_Circle_on_Point(Point(a,b),K))
        X.append(Tangent_to_Circle_on_Point(Point(a,-b),K))

    F=Translation_and_Rotate_Affine_Determine(Point(),Point(d,0),C.center,D.center)
    return [F[l] for l in X]

#=== 2つの円の位置関係を求める.
def Relationship_between_Circle_and_Circle(C: Circle, D:Circle) -> int:
    """ 2 つの円 C, D の位置関係を求める (返り値となる整数は 2 つの円の共通接線の本数と一致する).

    Args:
        C (Circle):
        D (Circle):

    Returns:
        int:
            4: 離れている
            3: 外接
            2: 交わっている
            1: 内接
            0: 含んでいる
    """

    d=abs(C.center-D.center)
    r=C.radius; s=D.radius

    alpha=compare(d,r+s)
    if alpha==1:
        return 4
    elif alpha==0:
        return 3
    else:
        beta=compare(d,abs(r-s))
        if beta==1:
            return 2
        elif beta==0:
            return 1
        else:
            return 0

#=== 共通部分
def Circles_Intersection_Area(C: Circle, D: Circle) -> float:
    """ 2つの円 C, D の共通部分の面積を求める.

    Args:
        C (Circle): 円
        D (Circle): 円

    Returns:
        float: 円 C と円 D の共通部分の面積
    """

    d = abs(C.center - D.center)
    r = C.radius
    s = D.radius

    if compare(d, r + s) == 1:
        # 2 つは離れている
        return 0

    if compare(d, abs(r - s)) == -1:
        # 一方が他方を含んでいる
        a = min(r, s)
        return pi * a * a

    alpha = acos((d * d + r * r - s * s) / (2 * d * r))
    beta = acos((d * d - r * r + s * s) / (2 * d * s))

    X = r *r * alpha
    Y = s * s * beta
    Z = d * r * sin(alpha)
    return X + Y - Z
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError
Back to top page