Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Intersection of a Circle and a Polygon

  Find the area of intersection between a circle $c$ and a polygon $g$. The center coordinate of the circle is ($0, 0$).

  The polygon $g$ is represented by a sequence of points $p_1$, $p_2$,..., $p_n$ where line segments connecting $p_i$ and $p_{i+1}$ ($1 \leq i \leq n−1$) are sides of the polygon. The line segment connecting $p_n$ and $p_1$ is also a side of the polygon.
  

Note that the polygon is not necessarily convex.
  

Input

The input is given in the following format.

  

$n$ $r$

$x_1$ $y_1$

$x_2$ $y_2$

 :

$x_n$ $y_n$

  In the first line, an integer n representing the number of points in the polygon is given. The coordinate of a point $p_i$ is given by two integers $x_i$ and $y_i$. The coordinates of the points are given in the order of counter-clockwise visit of them. All input values are given in integers.

Constraints

  
$3 \leq n \leq 100$

  
$1 \leq r \leq 100$

  
$-100 \leq x_i, y_i \leq 100$

Output

  Print the area of intersection in a line.
  The output values should be in a decimal fraction with an error less than 0.00001.

Sample Input 1

3 5
1 1
4 1
5 5

Sample Output 1

4.639858417607

Sample Input 2

4 5
0 0
-3 -6
1 -3
5 -4

Sample Output 2

11.787686807576



Sample input:
3 5
1 1
4 1
5 5


Sample output:
4.639858417607

Submission status: Accepted

Solution code:
from math import acos, hypot, isclose, sqrt
from typing import List, Tuple


def intersection(circle: Tuple[int, int, int],
                 polygon: List[Tuple[float, float]]) -> float:
    x, y, r = circle
    area = 0.0

    for p1, p2 in zip(polygon, polygon[1:] + [polygon[0]]):
        ps = seg_intersection(circle, (p1, p2))
        for pp1, pp2 in zip([p1] + ps, ps + [p2]):
            c = cross(pp1, pp2)
            if c == 0:
                continue
            d1 = hypot(*pp1)
            d2 = hypot(*pp2)
            if le(d1, r) and le(d2, r):
                area += c / 2
            else:
                t = acos(dot(pp1, pp2) / (d1 * d2))
                sign = c // abs(c)
                area += sign * r * r * t / 2

    return area


def cross(v1: Tuple[float, float], v2: Tuple[float, float]) -> float:
    x1, y1 = v1
    x2, y2 = v2
    return x1 * y2 - x2 * y1


def dot(v1: Tuple[float, float], v2: Tuple[float, float]) -> float:
    x1, y1 = v1
    x2, y2 = v2
    return x1 * x2 + y1 * y2


def seg_intersection(circle: Tuple[int, int, int],
                     seg: Tuple[Tuple[float, float],
                                Tuple[float, float]]) -> List[Tuple[float, float]]:
    x0, y0, r = circle
    p1, p2 = seg
    x1, y1 = p1
    x2, y2 = p2

    p1p2 = (x2 - x1) ** 2 + (y2 - y1) ** 2
    op1 = (x1 - x0) ** 2 + (y1 - y0) ** 2
    rr = r * r
    dp = dot((x1 - x0, y1 - y0), (x2 - x1, y2 - y1))

    d = dp * dp - p1p2 * (op1 - rr)
    ps = []

    if isclose(d, 0.0, abs_tol=1e-9):
        t = - dp / p1p2
        if ge(t, 0.0) and le(t, 1.0):
            ps.append((x1 + t * (x2 - x1), y1 + t * (y2 - y1)))
    elif d > 0.0:
        t1 = (- dp - sqrt(d)) / p1p2
        if ge(t1, 0.0) and le(t1, 1.0):
            ps.append((x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)))
        t2 = (- dp + sqrt(d)) / p1p2
        if ge(t2, 0.0) and le(t2, 1.0):
            ps.append((x1 + t2 * (x2 - x1), y1 + t2 * (y2 - y1)))

    return ps


def le(f1: float, f2: float) -> bool:
    return f1 < f2 or isclose(f1, f2, abs_tol=1e-9)


def ge(f1: float, f2: float) -> bool:
    return f1 > f2 or isclose(f1, f2, abs_tol=1e-9)


if __name__ == "__main__":
    n, r = [int(i) for i in input().split()]
    ps: List[Tuple[float, float]] = []

    for _ in range(n):
        x, y = map(lambda x: float(x), input().split())
        ps.append((x, y))

    print("{:.6f}".format(intersection((0, 0, r), ps)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# CGL_7_H: Circles - Intersection of a Circle and a Polygon

from math import acos, hypot, isclose, sqrt


def intersection(circle, polygon):
    x, y, r = circle
    area = 0.0

    for p1, p2 in zip(polygon, polygon[1:]+[polygon[0]]):
        ps = seg_intersection(circle, (p1, p2))
        for pp1, pp2 in zip([p1] + ps, ps + [p2]):
            c = cross(pp1, pp2)
            if c == 0:
                continue
            d1 = hypot(*pp1)
            d2 = hypot(*pp2)
            if le(d1, r) and le(d2, r):
                area += c / 2
            else:
                t = acos(dot(pp1, pp2) / (d1 * d2))
                sign = c // abs(c)
                area += sign * r * r * t / 2

    return area


def cross(v1, v2):
    x1, y1 = v1
    x2, y2 = v2
    return x1*y2 - x2*y1


def dot(v1, v2):
    x1, y1 = v1
    x2, y2 = v2
    return x1*x2 + y1*y2


def seg_intersection(circle, seg):
    x0, y0, r = circle
    p1, p2 = seg
    x1, y1 = p1
    x2, y2 = p2

    p1p2 = (x2-x1)**2 + (y2-y1)**2
    op1 = (x1-x0)**2 + (y1-y0)**2
    rr = r*r
    dp = dot((x1-x0, y1-y0), (x2-x1, y2-y1))

    d = dp*dp - p1p2*(op1 - rr)
    ps = []

    if isclose(d, 0.0, abs_tol=1e-9):
        t = -dp / p1p2
        if ge(t, 0.0) and le(t, 1.0):
            ps.append((x1 + t*(x2-x1), y1 + t*(y2-y1)))
    elif d > 0.0:
        t1 = (-dp-sqrt(d)) / p1p2
        if ge(t1, 0.0) and le(t1, 1.0):
            ps.append((x1 + t1*(x2-x1), y1 + t1*(y2-y1)))
        t2 = (-dp+sqrt(d)) / p1p2
        if ge(t2, 0.0) and le(t2, 1.0):
            ps.append((x1 + t2*(x2-x1), y1 + t2*(y2-y1)))

    # assert all(isclose(r, hypot(x, y)) for x, y in ps)
    return ps


def le(f1, f2):
    return f1 < f2 or isclose(f1, f2, abs_tol=1e-9)


def ge(f1, f2):
    return f1 > f2 or isclose(f1, f2, abs_tol=1e-9)


def eliminate_minus_zero(f):
    if isclose(f, 0.0, abs_tol=1e-9):
        return 0.0
    else:
        return f


def run():
    n, r = [int(i) for i in input().split()]
    ps = []

    for _ in range(n):
        x, y = [int(i) for i in input().split()]
        ps.append((x, y))

    print("{:.10f}".format(eliminate_minus_zero(intersection((0, 0, r), ps))))


if __name__ == '__main__':
    run()