Problem:
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

Solution (Python):
n, r = map(int, raw_input().split())
P = [map(int, raw_input().split()) for i in xrange(n)]

from math import sqrt, atan2

def intersection01(cx, cy, r, x1, y1, x2, y2):
    xd = x2 - x1; yd = y2 - y1
    X = x1 - cx; Y = y1 - cy
    a = xd**2 + yd**2
    b = xd * X + yd * Y
    c = X**2 + Y**2 - r**2
    D = b**2 - a*c
    result = []
    if D > 0:
        d = sqrt(D)
        if 0 < -b - d < a:
            s = (-b - d) / a
            result.append((x1 + xd*s, y1 + yd*s))
        if 0 < -b + d < a:
            s = (-b + d) / a
            result.append((x1 + xd*s, y1 + yd*s))
    elif D == 0:
        if 0 < -b < a:
            s = -b / float(a)
            result.append((x1 + xd*s, y1 + yd*s))
    return result

def calc(x0, y0, x1, y1, rr):
    if x0**2 + y0**2 - rr <= 1e-8 and x1**2 + y1**2 - rr <= 1e-8:
        return (x0 * y1 - x1 * y0) / 2.
    theta = atan2(x0*y1 - x1*y0, x0*x1 + y0*y1)
    return theta*rr/2.

rr = r**2
ans = 0
for i in xrange(n):
    (x0, y0) = P[i-1]; (x1, y1) = P[i]

    result = intersection01(0, 0, r, x0, y0, x1, y1)
    px = x0; py = y0
    for x, y in result:
        ans += calc(px, py, x, y, rr)
        px = x; py = y
    ans += calc(px, py, x1, y1, rr)
print "%.08f" % ans

Solution (Python):
import cmath
import itertools
import math
from collections import defaultdict

INF = float("inf")
PI = cmath.pi
TAU = cmath.pi * 2
EPS = 1e-10


class Point:
 """
 2次元空間上の点
 """

 
 CCW_COUNTER_CLOCKWISE = 1
 
 CCW_CLOCKWISE = -1
 
 CCW_ONLINE_BACK = 2
 
 CCW_ONLINE_FRONT = -2
 
 CCW_ON_SEGMENT = 0

 def __init__(self, x: float, y: float):
  self.c = complex(x, y)

 @property
 def x(self):
  return self.c.real

 @property
 def y(self):
  return self.c.imag

 @staticmethod
 def from_complex(c: complex):
  return Point(c.real, c.imag)

 @staticmethod
 def from_polar(r: float, phi: float):
  c = cmath.rect(r, phi)
  return Point(c.real, c.imag)

 def __add__(self, p):
  """
  :param Point p:
  """
  c = self.c + p.c
  return Point(c.real, c.imag)

 def __iadd__(self, p):
  """
  :param Point p:
  """
  self.c += p.c
  return self

 def __sub__(self, p):
  """
  :param Point p:
  """
  c = self.c - p.c
  return Point(c.real, c.imag)

 def __isub__(self, p):
  """
  :param Point p:
  """
  self.c -= p.c
  return self

 def __mul__(self, f: float):
  c = self.c * f
  return Point(c.real, c.imag)

 def __imul__(self, f: float):
  self.c *= f
  return self

 def __truediv__(self, f: float):
  c = self.c / f
  return Point(c.real, c.imag)

 def __itruediv__(self, f: float):
  self.c /= f
  return self

 def __repr__(self):
  return "({}, {})".format(round(self.x, 10), round(self.y, 10))

 def __neg__(self):
  c = -self.c
  return Point(c.real, c.imag)

 def __eq__(self, p):
  return abs(self.c - p.c) < EPS

 def __abs__(self):
  return abs(self.c)

 @staticmethod
 def ccw(a, b, c):
  """
  線分 ab に対する c の位置
  線分上にあるか判定するだけなら on_segment とかのが速い
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C&lang=ja
  :param Point a:
  :param Point b:
  :param Point c:
  """
  b = b - a
  c = c - a
  det = b.det(c)
  if det > EPS:
   return Point.CCW_COUNTER_CLOCKWISE
  if det < -EPS:
   return Point.CCW_CLOCKWISE
  if b.dot(c) < -EPS:
   return Point.CCW_ONLINE_BACK
  if c.norm() - b.norm() > EPS:
   return Point.CCW_ONLINE_FRONT
  return Point.CCW_ON_SEGMENT

 def dot(self, p):
  """
  内積
  :param Point p:
  :rtype: float
  """
  return self.x * p.x + self.y * p.y

 def det(self, p):
  """
  外積
  :param Point p:
  :rtype: float
  """
  return self.x * p.y - self.y * p.x

 def dist(self, p):
  """
  距離
  :param Point p:
  :rtype: float
  """
  return abs(self.c - p.c)

 def norm(self):
  """
  原点からの距離
  :rtype: float
  """
  return abs(self.c)

 def phase(self):
  """
  原点からの角度
  :rtype: float
  """
  return cmath.phase(self.c)

 def angle(self, p, q):
  """
  p に向いてる状態から q まで反時計回りに回転するときの角度
  -pi <= ret <= pi
  :param Point p:
  :param Point q:
  :rtype: float
  """
  return (cmath.phase(q.c - self.c) - cmath.phase(p.c - self.c) + PI) % TAU - PI

 def area(self, p, q):
  """
  p, q となす三角形の面積
  :param Point p:
  :param Point q:
  :rtype: float
  """
  return abs((p - self).det(q - self) / 2)

 def projection_point(self, p, q, allow_outer=False):
  """
  線分 pq を通る直線上に垂線をおろしたときの足の座標
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_A&lang=ja
  :param Point p:
  :param Point q:
  :param allow_outer: 答えが線分の間になくても OK
  :rtype: Point|None
  """
  diff_q = q - p
  
  r = (self - p).dot(diff_q) / abs(diff_q)
  
  phase = diff_q.phase()

  ret = Point.from_polar(r, phase) + p
  if allow_outer or (p - ret).dot(q - ret) < EPS:
   return ret
  return None

 def reflection_point(self, p, q):
  """
  直線 pq を挟んで反対にある点
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_B&lang=ja
  :param Point p:
  :param Point q:
  :rtype: Point
  """
  
  r = abs(self - p)
  
  angle = p.angle(q, self)
  
  angle = (q - p).phase() - angle
  return Point.from_polar(r, angle) + p

 def on_segment(self, p, q, allow_side=True):
  """
  点が線分 pq の上に乗っているか
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C&lang=ja
  :param Point p:
  :param Point q:
  :param allow_side: 端っこでギリギリ触れているのを許容するか
  :rtype: bool
  """
  if not allow_side and (self == p or self == q):
   return False
  
  
  return abs((p - self).det(q - self)) < EPS and (p - self).dot(q - self) < EPS


class Line:
 """
 2次元空間上の直線
 """

 def __init__(self, a: float, b: float, c: float):
  """
  直線 ax + by + c = 0
  """
  self.a = a
  self.b = b
  self.c = c

 @staticmethod
 def from_gradient(grad: float, intercept: float):
  """
  直線 y = ax + b
  :param grad: 傾き
  :param intercept: 切片
  :return:
  """
  return Line(grad, -1, intercept)

 @staticmethod
 def from_segment(p1, p2):
  """
  :param Point p1:
  :param Point p2:
  """
  a = p2.y - p1.y
  b = p1.x - p2.x
  c = p2.y * (p2.x - p1.x) - p2.x * (p2.y - p1.y)
  return Line(a, b, c)

 @property
 def gradient(self):
  """
  傾き
  """
  return INF if self.b == 0 else -self.a / self.b

 @property
 def intercept(self):
  """
  切片
  """
  return INF if self.b == 0 else -self.c / self.b

 def is_parallel_to(self, l):
  """
  平行かどうか
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A&lang=ja
  :param Line l:
  """
  
  return abs(Point.from_rect(self.a, self.b).det(Point.from_rect(l.a, l.b))) < EPS

 def is_orthogonal_to(self, l):
  """
  直行しているかどうか
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A&lang=ja
  :param Line l:
  """
  
  return abs(Point.from_rect(self.a, self.b).dot(Point.from_rect(l.a, l.b))) < EPS

 def intersection_point(self, l):
  """
  交差する点
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_C&lang=ja
  :param Line l:
  :rtype: Point|None
  """
  a1, b1, c1 = self.a, self.b, self.c
  a2, b2, c2 = l.a, l.b, l.c
  det = a1 * b2 - a2 * b1
  if abs(det) < EPS:
   
   return None
  x = (b1 * c2 - b2 * c1) / det
  y = (a2 * c1 - a1 * c2) / det
  return Point.from_rect(x, y)

 def dist(self, p):
  """
  他の点との最短距離
  :param Point p:
  """
  raise NotImplementedError()

 def has_point(self, p):
  """
  p が直線上に乗っているかどうか
  :param Point p:
  """
  return abs(self.a * p.x + self.b * p.y + self.c) < EPS


class Segment:
 """
 2次元空間上の線分
 """

 def __init__(self, p1, p2):
  """
  :param Point p1:
  :param Point p2:
  """
  self.p1 = p1
  self.p2 = p2

 def norm(self):
  """
  線分の長さ
  """
  return abs(self.p1 - self.p2)

 def phase(self):
  """
  p1 を原点としたときの p2 の角度
  """
  return (self.p2 - self.p1).phase()

 def is_parallel_to(self, s):
  """
  平行かどうか
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A&lang=ja
  :param Segment s:
  :return:
  """
  
  return abs((self.p1 - self.p2).det(s.p1 - s.p2)) < EPS

 def is_orthogonal_to(self, s):
  """
  直行しているかどうか
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A&lang=ja
  :param Segment s:
  :return:
  """
  
  return abs((self.p1 - self.p2).dot(s.p1 - s.p2)) < EPS

 def intersects_with(self, s, allow_side=True):
  """
  交差するかどうか
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B&lang=ja
  :param Segment s:
  :param allow_side: 端っこでギリギリ触れているのを許容するか
  """
  if self.is_parallel_to(s):
   
   return (s.p1.on_segment(self.p1, self.p2, allow_side) or
     s.p2.on_segment(self.p1, self.p2, allow_side) or
     self.p1.on_segment(s.p1, s.p2, allow_side) or
     self.p2.on_segment(s.p1, s.p2, allow_side))
  else:
   
   det_upper = EPS if allow_side else -EPS
   ok = True
   
   ok &= (self.p2 - self.p1).det(s.p1 - self.p1) * (self.p2 - self.p1).det(s.p2 - self.p1) < det_upper
   
   ok &= (s.p2 - s.p1).det(self.p1 - s.p1) * (s.p2 - s.p1).det(self.p2 - s.p1) < det_upper
   return ok

 def closest_point(self, p):
  """
  線分上の、p に最も近い点
  :param Point p:
  """
  
  d = (p - self.p1).dot(self.p2 - self.p1) / self.norm()
  
  if d < EPS:
   return self.p1
  
  if -EPS < d - self.norm():
   return self.p2
  
  return Point.from_polar(d, (self.p2 - self.p1).phase()) + self.p1

 def dist(self, p):
  """
  他の点との最短距離
  :param Point p:
  """
  return abs(p - self.closest_point(p))

 def dist_segment(self, s):
  """
  他の線分との最短距離
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_D&lang=ja
  :param Segment s:
  """
  if self.intersects_with(s):
   return 0.0
  return min(
   self.dist(s.p1),
   self.dist(s.p2),
   s.dist(self.p1),
   s.dist(self.p2),
  )

 def has_point(self, p, allow_side=True):
  """
  p が線分上に乗っているかどうか
  :param Point p:
  :param allow_side: 端っこでギリギリ触れているのを許容するか
  """
  return p.on_segment(self.p1, self.p2, allow_side=allow_side)


class Polygon:
 """
 2次元空間上の多角形
 """

 def __init__(self, points):
  """
  :param list of Point points:
  """
  self.points = points

 def iter2(self):
  """
  隣り合う2点を順に返すイテレータ
  :rtype: typing.Iterator[(Point, Point)]
  """
  return zip(self.points, self.points[1:] + self.points[:1])

 def iter3(self):
  """
  隣り合う3点を順に返すイテレータ
  :rtype: typing.Iterator[(Point, Point, Point)]
  """
  return zip(self.points,
       self.points[1:] + self.points[:1],
       self.points[2:] + self.points[:2])

 def area(self):
  """
  面積
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_A&lang=ja
  """
  
  dets = []
  for p, q in self.iter2():
   dets.append(p.det(q))
  return abs(math.fsum(dets)) / 2

 def is_convex(self, allow_straight=False, allow_collapsed=False):
  """
  凸多角形かどうか
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_B&lang=ja
  :param allow_straight: 3点がまっすぐ並んでるのを許容するかどうか
  :param allow_collapsed: 面積がゼロの場合を許容するか
  """
  ccw = []
  for a, b, c in self.iter3():
   ccw.append(Point.ccw(a, b, c))
  ccw = set(ccw)
  if len(ccw) == 1:
   if ccw == {Point.CCW_CLOCKWISE}:
    return True
   if ccw == {Point.CCW_COUNTER_CLOCKWISE}:
    return True
  if allow_straight and len(ccw) == 2:
   if ccw == {Point.CCW_ONLINE_FRONT, Point.CCW_CLOCKWISE}:
    return True
   if ccw == {Point.CCW_ONLINE_FRONT, Point.CCW_COUNTER_CLOCKWISE}:
    return True
  if allow_collapsed and len(ccw) == 3:
   return ccw == {Point.CCW_ONLINE_FRONT, Point.CCW_ONLINE_BACK, Point.CCW_ON_SEGMENT}
  return False

 def has_point_on_edge(self, p):
  """
  指定した点が辺上にあるか
  :param Point p:
  :rtype: bool
  """
  for a, b in self.iter2():
   if p.on_segment(a, b):
    return True
  return False

 def contains(self, p, allow_on_edge=True):
  """
  指定した点を含むか
  Winding Number Algorithm
  https://www.nttpc.co.jp/technology/number_algorithm.html
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_C&lang=ja
  :param Point p:
  :param bool allow_on_edge: 辺上の点を許容するか
  """
  angles = []
  for a, b in self.iter2():
   if p.on_segment(a, b):
    return allow_on_edge
   angles.append(p.angle(a, b))
  
  return abs(math.fsum(angles)) > EPS

 @staticmethod
 def convex_hull(points, allow_straight=False):
  """
  凸包。x が最も小さい点のうち y が最も小さい点から反時計回り。
  Graham Scan O(N log N)
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A&lang=ja
  :param list of Point points:
  :param allow_straight: 3点がまっすぐ並んでるのを許容するかどうか
  :rtype: list of Point
  """
  points = points[:]
  points.sort(key=lambda p: (p.x, p.y))

  
  det_lower = -EPS if allow_straight else EPS

  sz = 0
  
  ret = [None] * (len(points) * 2)
  for p in points:
   while sz > 1 and (ret[sz - 1] - ret[sz - 2]).det(p - ret[sz - 1]) < det_lower:
    sz -= 1
   ret[sz] = p
   sz += 1
  floor = sz
  for p in reversed(points[:-1]):
   while sz > floor and (ret[sz - 1] - ret[sz - 2]).det(p - ret[sz - 1]) < det_lower:
    sz -= 1
   ret[sz] = p
   sz += 1
  ret = ret[:sz - 1]

  if allow_straight and len(ret) > len(points):
   
   ret = points
  return ret

 @staticmethod
 def diameter(points):
  """
  直径
  凸包構築 O(N log N) + カリパー法 O(N)
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_B&lang=ja
  :param list of Point points:
  """
  
  points = Polygon.convex_hull(points, allow_straight=False)
  if len(points) == 1:
   return 0.0
  if len(points) == 2:
   return abs(points[0] - points[1])

  
  si = points.index(min(points, key=lambda p: (p.x, p.y)))
  sj = points.index(max(points, key=lambda p: (p.x, p.y)))
  n = len(points)

  ret = 0.0
  
  i, j = si, sj
  while i != sj or j != si:
   ret = max(ret, abs(points[i] - points[j]))
   ni = (i + 1) % n
   nj = (j + 1) % n
   
   if (points[ni] - points[i]).det(points[nj] - points[j]) > 0:
    j = nj
   else:
    i = ni
  return ret

 def convex_cut_by_line(self, line_p1, line_p2):
  """
  凸多角形を直線 line_p1-line_p2 でカットする。
  凸じゃないといけません
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_C&lang=ja
  :param line_p1:
  :param line_p2:
  :return: (line_p1-line_p2 の左側の多角形, line_p1-line_p2 の右側の多角形)
  :rtype: (Polygon|None, Polygon|None)
  """
  n = len(self.points)
  line = Line.from_segment(line_p1, line_p2)
  
  on_line_points = []
  for i, p in enumerate(self.points):
   if line.has_point(p):
    on_line_points.append(i)

  
  has_on_line_edge = False
  if len(on_line_points) >= 3:
   has_on_line_edge = True
  elif len(on_line_points) == 2:
   
   has_on_line_edge = abs(on_line_points[0] - on_line_points[1]) in [1, n - 1]
  
  if has_on_line_edge:
   for p in self.points:
    ccw = Point.ccw(line_p1, line_p2, p)
    if ccw == Point.CCW_COUNTER_CLOCKWISE:
     return Polygon(self.points[:]), None
    if ccw == Point.CCW_CLOCKWISE:
     return None, Polygon(self.points[:])

  ret_lefts = []
  ret_rights = []
  d = line_p2 - line_p1
  for p, q in self.iter2():
   det_p = d.det(p - line_p1)
   det_q = d.det(q - line_p1)
   if det_p > -EPS:
    ret_lefts.append(p)
   if det_p < EPS:
    ret_rights.append(p)
   
   if det_p * det_q < -EPS:
    intersection = line.intersection_point(Line.from_segment(p, q))
    ret_lefts.append(intersection)
    ret_rights.append(intersection)

  
  l = Polygon(ret_lefts) if len(ret_lefts) > 1 else None
  r = Polygon(ret_rights) if len(ret_rights) > 1 else None
  return l, r


def closest_pair(points):
 """
 最近点対 O(N log N)
 Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_5_A&lang=ja
 :param list of Point points:
 :rtype: (float, (Point, Point))
 :return: (距離, 点対)
 """
 assert len(points) >= 2

 def _rec(xsorted):
  """
  :param list of Point xsorted:
  :rtype: (float, (Point, Point))
  """
  n = len(xsorted)
  if n <= 2:
   return xsorted[0].dist(xsorted[1]), (xsorted[0], xsorted[1])
  if n <= 3:
   
   d = INF
   pair = None
   for p, q in itertools.combinations(xsorted, r=2):
    if p.dist(q) < d:
     d = p.dist(q)
     pair = p, q
   return d, pair

  
  
  ld, lp = _rec(xsorted[:n // 2])
  rd, rp = _rec(xsorted[n // 2:])
  if ld <= rd:
   d = ld
   ret_pair = lp
  else:
   d = rd
   ret_pair = rp

  mid_x = xsorted[n // 2].x
  
  mid_points = []
  for p in xsorted:
   
   if abs(p.x - mid_x) - d < -EPS:
    mid_points.append(p)

  
  mid_points.sort(key=lambda p: p.y)
  mid_n = len(mid_points)
  for i in range(mid_n - 1):
   j = i + 1
   p = mid_points[i]
   q = mid_points[j]
   
   while (q.y - p.y) - d < -EPS:
    pq_d = p.dist(q)
    if pq_d < d:
     d = pq_d
     ret_pair = p, q
    j += 1
    if j >= mid_n:
     break
    q = mid_points[j]
  return d, ret_pair

 return _rec(list(sorted(points, key=lambda p: p.x)))


def closest_pair_randomized(points):
 """
 最近点対 乱択版 O(N)
 http://ir5.hatenablog.com/entry/20131221/1387557630
 グリッドの管理が dict だから定数倍気になる
 Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_5_A&lang=ja
 :param list of Point points:
 :rtype: (float, (Point, Point))
 :return: (距離, 点対)
 """
 n = len(points)
 assert n >= 2
 if n == 2:
  return points[0].dist(points[1]), (points[0], points[1])

 
 import random
 points = points[:]
 random.shuffle(points)

 DELTA_XY = list(itertools.product([-1, 0, 1], repeat=2))
 grid = defaultdict(list)
 delta = INF
 dist = points[0].dist(points[1])
 ret_pair = points[0], points[1]
 for i in range(2, n):
  if delta < EPS:
   return 0.0, ret_pair
  
  
  if dist - delta < -EPS:
   delta = dist
   grid = defaultdict(list)
   for a in points[:i]:
    grid[a.x // delta, a.y // delta].append(a)
  else:
   p = points[i - 1]
   grid[p.x // delta, p.y // delta].append(p)

  p = points[i]
  dist = delta
  grid_x = p.x // delta
  grid_y = p.y // delta
  
  for dx, dy in DELTA_XY:
   for q in grid[grid_x + dx, grid_y + dy]:
    d = p.dist(q)
    
    if d - dist < -EPS:
     dist = d
     ret_pair = p, q
 return min(delta, dist), ret_pair


class Circle:
 def __init__(self, o, r):
  """
  :param Point o:
  :param float r:
  """
  self.o = o
  self.r = r

 def __eq__(self, other):
  return self.o == other.o and abs(self.r - other.r) < EPS

 def ctc(self, c):
  """
  共通接線 common tangent の数
  4: 離れてる
  3: 外接
  2: 交わってる
  1: 内接
  0: 内包
  inf: 同一
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_A&lang=ja
  :param Circle c:
  :rtype: int
  """
  if self.o == c.o:
   return INF if abs(self.r - c.r) < EPS else 0
  
  d = self.o.dist(c.o) - self.r - c.r
  if d > EPS:
   return 4
  elif d > -EPS:
   return 3
  
  elif d + min(self.r, c.r) * 2 > EPS:
   return 2
  elif d + min(self.r, c.r) * 2 > -EPS:
   return 1
  return 0

 def has_point_on_edge(self, p):
  """
  指定した点が円周上にあるか
  :param Point p:
  :rtype: bool
  """
  return abs(self.o.dist(p) - self.r) < EPS

 def contains(self, p, allow_on_edge=True):
  """
  指定した点を含むか
  :param Point p:
  :param bool allow_on_edge: 辺上の点を許容するか
  """
  if allow_on_edge:
   
   return self.o.dist(p) - self.r < EPS
  else:
   
   return self.o.dist(p) - self.r < -EPS

 def area(self):
  """
  面積
  """
  return self.r ** 2 * PI

 def circular_segment_area(self, angle):
  """
  弓形⌓の面積
  :param float angle: 角度ラジアン
  """
  
  sector_area = self.area() * angle / TAU
  
  return sector_area - self.r ** 2 * math.sin(angle) / 2

 def intersection_points(self, other, allow_outer=False):
  """
  :param Segment|Circle other:
  :param bool allow_outer:
  """
  if isinstance(other, Segment):
   return self.intersection_points_with_segment(other, allow_outer=allow_outer)
  if isinstance(other, Circle):
   return self.intersection_points_with_circle(other)
  raise NotImplementedError()

 def intersection_points_with_segment(self, s, allow_outer=False):
  """
  線分と交差する点のリスト
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_D&lang=ja
  :param Segment s:
  :param bool allow_outer: 線分の間にない点を含む
  :rtype: list of Point
  """
  
  projection_point = self.o.projection_point(s.p1, s.p2, allow_outer=True)
  
  dist = self.o.dist(projection_point)
  
  if dist - self.r > EPS:
   return []
  if dist - self.r > -EPS:
   if allow_outer or s.has_point(projection_point):
    return [projection_point]
   else:
    return []
  
  diff = Point.from_polar(math.sqrt(self.r ** 2 - dist ** 2), s.phase())
  ret1 = projection_point + diff
  ret2 = projection_point - diff
  ret = []
  if allow_outer or s.has_point(ret1):
   ret.append(ret1)
  if allow_outer or s.has_point(ret2):
   ret.append(ret2)
  return ret

 def intersection_points_with_circle(self, other):
  """
  円と交差する点のリスト
  Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_E&langja
  :param circle other:
  :rtype: list of Point
  """
  ctc = self.ctc(other)
  if not 1 <= ctc <= 3:
   return []
  if ctc == 3:
   
   return [Point.from_polar(self.r, (other.o - self.o).phase()) + self.o]
  if ctc == 1:
   
   if self.r > other.r:
    return [Point.from_polar(self.r, (other.o - self.o).phase()) + self.o]
   else:
    return [Point.from_polar(self.r, (self.o - other.o).phase()) + self.o]
  
  assert ctc == 2

  a = other.r
  b = self.r
  c = self.o.dist(other.o)
  
  cos_a = (b ** 2 + c ** 2 - a ** 2) / (2 * b * c)
  angle = math.acos(cos_a)
  phi = (other.o - self.o).phase()
  return [
   self.o + Point.from_polar(self.r, phi + angle),
   self.o + Point.from_polar(self.r, phi - angle),
  ]

 def tangent_points_with_point(self, p):
  """
  p を通る接線との接点
  :param Point p:
  :rtype: list of Point
  """
  dist = self.o.dist(p)
  
  if dist - self.r < -EPS:
   
   return []
  if dist - self.r < EPS:
   
   return [Point(p.x, p.y)]

  a = math.sqrt(dist ** 2 - self.r ** 2)
  b = self.r
  c = dist
  
  cos_a = (b ** 2 + c ** 2 - a ** 2) / (2 * b * c)
  angle = math.acos(cos_a)
  phi = (p - self.o).phase()
  return [
   self.o + Point.from_polar(self.r, phi + angle),
   self.o + Point.from_polar(self.r, phi - angle),
  ]

 def tangent_points_with_circle(self, other):
  """
  other との共通接線との接点
  :param Circle other:
  :rtype: list of Point
  """
  ctc = self.ctc(other)
  if ctc > 4:
   raise ValueError('2つの円が同一です')
  if ctc == 0:
   return []
  if ctc == 1:
   return self.intersection_points_with_circle(other)

  assert ctc in (2, 3, 4)
  ret = []
  
  
  if abs(self.r - other.r) < EPS:
   
   phi = (other.o - self.o).phase()
   ret.append(self.o + Point.from_polar(self.r, phi + PI / 2))
   ret.append(self.o + Point.from_polar(self.r, phi - PI / 2))
  else:
   
   intersection = self.o + (other.o - self.o) / (self.r - other.r) * self.r
   ret += self.tangent_points_with_point(intersection)

  
  
  intersection = self.o + (other.o - self.o) / (self.r + other.r) * self.r
  ret += self.tangent_points_with_point(intersection)
  return ret


def round_point(p):
 """
 8桁で四捨五入して、-0を0に変換する
 :param p:
 :return:
 """
 return round(p.x, 10) + 0, round(p.y, 10) + 0


def solve():
 import sys
 N, R = list(map(int, sys.stdin.buffer.readline().split()))
 XY = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

 circle = Circle(Point(0, 0), R)
 points = []
 for x, y in XY:
  points.append(Point(x, y))
 polygon = Polygon(points)

 
 points_with_on_circle = []
 for p, q in polygon.iter2():
  points_with_on_circle.append(p)
  s = Segment(p, q)
  intersections = circle.intersection_points_with_segment(s, allow_outer=False)
  
  intersections.sort(key=lambda ip: p.dist(ip))
  for ip in intersections:
   if ip != p and ip != q:
    points_with_on_circle.append(ip)

 outer_index = None
 for i, p in enumerate(points_with_on_circle):
  if not circle.contains(p, allow_on_edge=True):
   outer_index = i
   break
 
 if outer_index is None:
  return polygon.area()

 inner_index = None
 i = outer_index + 1
 while i != outer_index:
  j = (i + 1) % len(points_with_on_circle)
  p = points_with_on_circle[i]
  q = points_with_on_circle[j]
  if circle.contains(p, allow_on_edge=True) and circle.contains(q, allow_on_edge=True):
   inner_index = i
   break
  i = j
 
 if inner_index is None:
  return 0.0

 points_with_on_circle = points_with_on_circle[inner_index:] + points_with_on_circle[:inner_index]
 points_on_circle = []
 
 for pl, p, pr in Polygon(points_with_on_circle).iter3():
  if circle.has_point_on_edge(p) and (circle.contains(pl) or circle.contains(pr)):
   points_on_circle.append((p, not circle.contains(pr, allow_on_edge=True)))

 
 points_on_circle.sort(key=lambda pf: (pf[0] - circle.o).phase())
 seen = [False] * len(points_on_circle)

 ret = 0
 
 while not all(seen):
  partial_points = []
  i = seen.index(False)
  p, out = points_on_circle[i]
  seen[i] = True
  partial_points.append(p)
  j = points_with_on_circle.index(p)

  end_p = p
  first = True
  while first or p != end_p:
   
   if out:
    i = (i + 1) % len(points_on_circle)
    q, out = points_on_circle[i]
    ret += circle.circular_segment_area(circle.o.angle(p, q) % TAU)
    p = q
    partial_points.append(p)
    j = points_with_on_circle.index(p)
   else:
    j = (j + 1) % len(points_with_on_circle)
    p = points_with_on_circle[j]
    partial_points.append(p)

   if circle.has_point_on_edge(p):
    i = [i for i, (q, _) in enumerate(points_on_circle) if p == q][0]
    p, out = points_on_circle[i]
    if seen[i]:
     pp = [p]
     partial_points.pop()
     while partial_points and partial_points[-1] != p:
      pp.append(partial_points.pop())
     ret += Polygon(pp).area()
     out = True
    seen[i] = True
   first = False
 return ret


print(solve())

Solution (Python):
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)))

Solution (Python):



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)))

    
    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()