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

Constraints

* $3 \leq n \leq 100$
* $1 \leq r \leq 100$
* $-100 \leq x_i, y_i \leq 100$

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.

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.

Examples

Input

3 5
1 1
4 1
5 5


Output

4.639858417607


Input

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


Output

11.787686807576

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)

const double eps = 1e-10;
const double inf = 1e+10;
const double pi = acos(-1.0);

struct Point {
  double x, y;
  Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}  
  double norm() {return sqrt(x*x + y*y);}
};

Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
double operator * (const Point &p, const Point q) {return p.x * q.x + p.y * q.y;}
bool operator == (const Point &p, const Point &q) {return (abs(p.x - q.x) < eps && abs(p.y - q.y) < eps);}
bool operator != (const Point &p, const Point &q) {return !(p == q);}
double cross(const Point &p, const Point &q) {return p.x*q.y - p.y*q.x;}
double dist(const Point &p, const Point &q) {return (p-q).norm();}
bool compx(const Point &p, const Point &q) {return p.x != q.x? p.x < q.x : p.y < q.y;}
bool compy(const Point &p, const Point &q) {return p.y != q.y? p.y < q.y : p.x < q.x;}

struct Segment {
  Point p , q;
  Segment(Point p = Point(0.0,0.0), Point q = Point(0.0,0.0)) : p(p), q(q) {}
};

struct Line {
  double a, b, c;
  Line(double a, double b, double c) : a(a), b(b), c(c) {}
  Line(Point p, Point q) {
    a = q.y - p.y;
    b = p.x - q.x;
    c = q.x * p.y - p.x * q.y;
  }
};

struct Circle {
  double r;
  Point p;
  Circle(Point p = Point(0.0, 0.0), double r = 0.0) : p(p), r(r) {}
};

// 点の直線への射影
Point projection (Point p, Line l) {
  double x = p.x - l.a * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  double y = p.y - l.b * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  return Point(x,y);
}

// 線対称な点
Point reflection(Point p, Line l) {
  double x = p.x - 2.0 * l.a * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  double y = p.y - 2.0 * l.b * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  return Point(x,y);
}

// 点の線分からの回転方向 (1:半時計 -1:時計 2:同一直線後方 -2:同一直線前方 0:線分上)
int ccw(Point p, Point p1, Point p2) {
  p1 = p1 - p; p2 = p2 - p;
  if(cross(p1,p2) > eps) return 1; 
  if(cross(p1,p2) < -eps) return -1; 
  if(p1 * p2 < 0) return 2; 
  if(p1.norm() < p2.norm()) return -2; 
  return 0; 
}

// 点が線分上にあるか判定
bool on_segment(Point p, Segment s) {
  return (ccw(s.p,s.q,p) == 0 ? true : false);
}

// 線分の交差判定
bool segment_segment_cross(const Segment l, const Segment s) {
  return ccw(l.p,l.q,s.p) * ccw(l.p,l.q,s.q) <= 0 && ccw(s.p,s.q,l.p) * ccw(s.p,s.q,l.q) <= 0;
}

// 直線の平行・直交判定 (平行:2 直交:1 その他:0)
int line_parallel_orthogonal(Line l, Line s) {
  if(abs(l.a*s.a + l.b*s.b) < eps) return 1;
  else if(abs(l.a*s.b - l.b*s.a) < eps) return 2;
  else return 0;
}

// 直線と直線の交点 
vector<Point> line_line_cross(Line l, Line s) {
  vector<Point> vp;
  if(line_parallel_orthogonal(l,s) != 2) {
    Point p;
    p.x = (l.b*s.c - s.b*l.c) / (l.a*s.b - s.a*l.b);
    p.y = (-l.a*s.c + s.a*l.c) / (l.a*s.b - s.a*l.b);
    vp.push_back(p);
  }
  return vp;
}

// 点と直線の距離
double point_line_dist(Point p, Line l) {
  return abs(l.a*p.x + l.b*p.y + l.c) / sqrt(l.a*l.a + l.b*l.b);
}

// 点と線分の距離
double point_segment_dist(Point p, Segment s) {
  Point h = projection(p,Line(s.p,s.q));
  if(on_segment(h,s)) return dist(p,h);
  else return min(dist(p,s.p),dist(p,s.q));
}

// 線分と線分の距離
double segment_segment_dist(Segment l, Segment s) {
  if(segment_segment_cross(l,s)) return 0.0;
  else return min({point_segment_dist(l.p,s),point_segment_dist(l.q,s),point_segment_dist(s.p,l),point_segment_dist(s.q,l)});
}

// 直線と直線の距離
double line_line_dist(Line l, Line s) {
  if(line_parallel_orthogonal(l,s) != 2) return 0.0;
  else if(abs(s.a) < eps) return point_line_dist(Point(0.0,-s.c/s.b),l);
  else return point_line_dist(Point(-s.c/s.a,0),l);
}

// 直線と線分の距離
double line_segment_dist(Line l, Segment s) {
  Point a, b;
  if(abs(l.a) < eps) a = Point(0.0,-l.c/l.b), b = Point(1.0,-l.c/l.b);
  else if(abs(l.b) < eps) a = Point(-l.c/l.a,0.0), b = Point(-l.c/l.a,0.0);
  else a = Point(0.0,-l.c/l.b), b = Point(-l.c/l.a,0);

  if(ccw(a,b,s.p) * ccw(a,b,s.q) <= 0) return 0.0;
  else return min(point_line_dist(s.p,l),point_line_dist(s.q,l));
}

// ★円と円の交差判定 (離れる:4 外接:3 交わる:2 内接:1 内包:0)
int circle_circle_pos(Circle c, Circle d) {
  if(dist(c.p,d.p) >= c.r + d.r + eps) return 4;
  else if(abs(dist(c.p,d.p) - c.r - d.r) < eps) return 3;
  else if(dist(c.p,d.p) >= abs(c.r-d.r) + eps) return 2;
  else if(abs(dist(c.p,d.p) - abs(c.r-d.r)) < eps) return 1;
  else return 0; 
}

// ★円と直線の交点
vector<Point> circle_line_cross(Circle c, Line l) {
  vector<Point> vp;
  Point h = projection(c.p,l);

  double d = l.a*c.p.x + l.b*c.p.y + l.c;
  double q = c.r*c.r - d*d / (l.a*l.a + l.b*l.b);
  if(q >= eps) {
    Point p1, p2;
    p1.x = h.x + sqrt(q) * l.b / sqrt(l.a*l.a + l.b*l.b);
    p1.y = h.y - sqrt(q) * l.a / sqrt(l.a*l.a + l.b*l.b);
    p2.x = h.x - sqrt(q) * l.b / sqrt(l.a*l.a + l.b*l.b);
    p2.y = h.y + sqrt(q) * l.a / sqrt(l.a*l.a + l.b*l.b);
    vp.push_back(p1);
    vp.push_back(p2);
  } else if(abs(q) < eps) {
    vp.push_back(h);
  }
  return vp;
} 

// ★円と円の交点
vector<Point> circle_circle_cross(Circle c, Circle d) {
  if(circle_circle_pos(c,d)) {
    Line l(2.0*(c.p.x-d.p.x),2.0*(c.p.y-d.p.y),-c.p.x*c.p.x+d.p.x*d.p.x-c.p.y*c.p.y+d.p.y*d.p.y+c.r*c.r-d.r*d.r);
    return circle_line_cross(c,l);
  } else {
    return vector<Point>();
  }
}

// ★円の点Pを通る接線
vector<Line> tangent_to_circle(Circle c, Point p) {
  if(dist(c.p,p) < c.r - eps) return vector<Line>();
  Point q = p - c.p;
  vector<Point> v = circle_line_cross(c,Line(q.x,q.y,-(q*c.p+c.r*c.r)));
  vector<Line> l;
  for(auto t : v) {
    q = t - c.p;
    l.push_back(Line(q.x,q.y,-(q*c.p+c.r*c.r)));
  }
  return l;
}

// ★円と円の共通接線
vector<Line> common_tangent(Circle c, Circle d) {
  Point da = d.p - c.p;
  vector<Point> tin = circle_line_cross(Circle(Point(0.0,0.0),c.r),Line(da.x,da.y,-c.r*(c.r+d.r)));
  vector<Point> tout = circle_line_cross(Circle(Point(0.0,0.0),c.r),Line(da.x,da.y,-c.r*(c.r-d.r)));
  vector<Line> l;
  for(auto p : tin) {
    vector<Line> lin = tangent_to_circle(c,p+c.p);
    for(auto s : lin) l.push_back(s);
  }
  for(auto p : tout) {
    vector<Line> lout = tangent_to_circle(c,p+c.p);
    for(auto s : lout) l.push_back(s);
  }
  return l;
}

// ★多角形の面積
double polygon_area(vector<Point>& v) {
  int l = v.size();
  double s = 0.0;
  for(int i = 0; i < l; i++) s += 1/2.0 * cross(v[i],v[(i+1)%l]);
  return s;
}

// ★多角形の凸性
bool polygon_convex(vector<Point>& v) {
  int l = v.size();
  for(int i = 0; i < l; i++) {
    if(cross(v[(i+1)%l]-v[i],v[(i+2)%l]-v[i]) < -eps) return false;
  }
  return true;
} 

// ★点の多角形への包含 (含まれる:2 辺上:1 外:0)
int polygon_inclusion(const vector<Point>& v, const Point p) {
  int l = v.size();
  bool in = false;
  for(int i = 0; i < l; i++) {
    Point a = v[i] - p, b = v[(i+1)%l] - p;
    if(on_segment(Point(0.0,0.0),Segment(a,b))) return 1;
    if(a.y > b.y) swap(a,b);
    if(a.y <= 0 && b.y > 0 && cross(a,b) < 0) in = !in; 
  }
  return in ? 2 : 0;
}

// ★凸包 O(nlogn) (Graham Scan)
vector<Point> convex_hull(vector<Point>& v) {
  int l = v.size();
  sort(v.begin(),v.end(),compx);
  vector<Point> c(2*l);
  int k = 0;
  for(int i = 0; i < l; i++) {
    while(k > 1 && cross(c[k-1]-c[k-2],v[i]-c[k-1]) <= -eps) k--;
    c[k++] = v[i];
  }
  for(int i = l-2, t = k; i >= 0; i--) {
    while(k > t && cross(c[k-1]-c[k-2],v[i]-c[k-1]) <= -eps) k--;
    c[k++] = v[i];
  }
  c.resize(k-1);
  return c;
}

// ★凸多角形の切断(左側)
vector<Point> convex_cut(vector<Point>& v, Point a, Point b) {
  int n = v.size();
  vector<Point> res;
  for(int i = 0; i < n; i++) {
    Point now = v[i], next = v[(i+1)%n];
    if(ccw(a,b,now) != -1) res.push_back(now);
    if(ccw(a,b,now)*ccw(a,b,next) < 0) {
      vector<Point> c = line_line_cross(Line(a,b),Line(now,next));
      for(auto p : c) res.push_back(p);
    }
  }
  return res;
}

// ★最遠点距離(キャリパー法) O(n) (凸包を構成する場合O(nlogn))
double convex_diameter(vector<Point>& v) {
  vector<Point> c = convex_hull(v);
  int l = c.size();
  if(l == 2) return (dist(c[0],c[1]));
  int i = 0, j = 0;
  for(int k = 0; k < l; k++) {
    if(!compx(c[i],c[k])) i = k;
    if(compx(c[j],c[k])) j = k;
  }
  double res = 0.0;
  int si = i, sj = j;
  while(i != sj || j != si) {
    res = max(res,dist(c[i],c[j]));
    if(cross(c[(i+1)%l]-c[i],c[(j+1)%l]-c[j]) < 0) i = (i + 1) % l;
    else j = (j + 1) % l;
  }
  return res;
}

// ★最近接点距離 O(nlogn) x座標でsortして渡す.
double closest_pair(vector<Point>::iterator it, int n) {
  if(n <= 1) return inf;
  int m = n / 2;
  double x = it[m].x;
  double d = min(closest_pair(it,m),closest_pair(it+m,n-m));
  inplace_merge(it,it+m,it+n,compy);

  vector<Point> b;
  for(int i = 0; i < n; i++) {
    if(abs(it[i].x-x) >= d) continue;
    for(int j = 0; j < b.size(); j++) {
      double dx = it[i].x - b[b.size()-j-1].x;
      double dy = it[i].y - b[b.size()-j-1].y;
      if(dy >= d) break;
      d = min(d,sqrt(dx*dx+dy*dy));
    }
    b.push_back(it[i]);
  }
  return d;
}

double circle_triangle_area(const Point a, const Point b, double r, bool triangle) {
  if(triangle) {
    return 1 / 2.0 * cross(a,b);
  } else {
    double ang = atan2(cross(a,b),a*b);
    return r * r * ang / 2.0;
  }
}

// 円と多角形の共通部分面積
double circle_polygon_area(Circle& c, vector<Point>& v) {
  int n = v.size();
  double s = 0.0;
  for(int i = 0; i < n; i++) {
    Point a = v[i] - c.p, b = v[(i+1)%n] - c.p;
    bool ain = a.norm() < c.r + eps;
    bool bin = b.norm() < c.r + eps;
    if(ain && bin) {
      s += circle_triangle_area(a,b,c.r,true);
    } else {
      Circle oc(Point(0.0,0.0),c.r);
      vector<Point> cl = circle_line_cross(oc,Line(a,b)); 
      vector<Point> cs;
      for(auto p : cl) {
        if(on_segment(p,Segment(a,b))) cs.push_back(p); 
      }
      if(cs.empty()) {
        s += circle_triangle_area(a,b,c.r,false);
      } else {
        Point u = cs[0], t = cs.back();
        if(dist(a,u) > dist(b,u)) swap(u,t);
        s += circle_triangle_area(u,t,c.r,true) + circle_triangle_area(a,u,c.r,ain) + circle_triangle_area(t,b,c.r,bin);
      }
    }
  }
  return s;
}

int main() {
  int n;
  Circle c;
  cin >> n >> c.r;
  vector<Point> v(n);
  rep(i,n) cin >> v[i].x >> v[i].y;
  printf("%.9lf\n",circle_polygon_area(c,v));
  return 0;
}