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>
#define ll long long
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define pa pair<int,int>
const int N=1e6+10;
const int mod=1e9+7;
using namespace std;

const double eps=1e-8,pi=acos(-1.0);
inline int sgn(double x){return x<-eps?-1:(x>eps?1:0);}
inline double pf(double x){return x*x;}
struct Point
{
   double x,y;
   Point(){x=y=0.0;}
   Point(double x,double y):x(x),y(y){}
   Point(pair<double,double> p):x(p.first),y(p.second){}
   Point operator + (Point b){return Point(x+b.x,y+b.y);}
   Point operator - (Point b){return Point(x-b.x,y-b.y);}
   Point operator * (double mul){return Point(x*mul,y*mul);}
   Point operator / (double div){return Point(x/div,y/div);}
   bool operator == (const Point& p)const {return sgn(x-p.x)==0&&sgn(y-p.y)==0;}
   bool operator != (const Point& p)const {return sgn(x-p.x)!=0||sgn(y-p.y)!=0;}
   double length()const {return sqrt(pf(x)+pf(y));}
   double angle()const{return atan2(y,x);}
};
typedef Point Vector;
typedef vector<Point> Polygon;
inline double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline double dis(Vector a,Vector b){return sqrt(pf(a.x-b.x)+pf(a.y-b.y));}
inline double angle(Vector a,Vector b){return acos(dot(a,b)/a.length()/b.length());}
Vector rot(Vector a,double rad){return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}//ni shi zhen
Vector unit(Vector v){return v/v.length();}// 单位向量
Vector normal(Vector a){return Vector(-a.y,a.x);} // 法向量
struct circle
{
   Point p; double r;
   circle(){}
   circle(Point p,double r):p(p),r(r){}
};
struct line
{
   Point a,b;
   line(){}
   line(Point a,Point b):a(a),b(b){}
};
int circle_position(circle c1,circle c2)
{
    double d=pf(c1.p.x-c2.p.x)+pf(c1.p.y-c2.p.y);
    if(d>pf(c1.r+c2.r)) return 4;
    if(d==pf(c1.r+c2.r)) return 3;
    if(d==pf(c1.r-c2.r)) return 1;
    if(d<pf(c1.r-c2.r)) return 0;
    return 2;
}
// 点和线段的关系
int ccw(Point p0,Point p1,Point p2) // p0-p1, p2
{
    Vector a=p1-p0,b=p2-p0; 
    if(cross(a,b)>eps) return 1;        // counter_clockwise
    if(cross(a,b)<-eps) return -1;      // clockwise
    if(dot(a,b)<-eps) return 2;         // online_back
    if(a.length()<b.length()) return -2;// online_front 
    return 0;                           // online_segment
}
bool intersect(Point a,Point b,Point A,Point B)
{
    return (ccw(a,b,A)*ccw(a,b,B)<=0&&ccw(A,B,a)*ccw(A,B,b)<=0);
}
Point cal_cross_point(Point a,Point b,Point A,Point B)
{
    // double x1=a.x,x2=b.x,x3=A.x,x4=B.x;
    // double y1=a.y,y2=b.y,y3=A.y,y4=B.y;
    // Point ret;
    // ret.x = ((x2-x1)*(y3*(x4-x3)+x3*(y3-y4))-(x4-x3)*(y1*(x2-x1)+x1*(y1-y2)))/((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1));
    // if(x1 != x2){
    //     ret.y = ((y2-y1)*ret.x+y1*(x2-x1)+x1*(y1-y2))/(x2-x1);
    // }else{
    //     ret.y = ((y4-y3)*ret.x+y3*(x4-x3)+x3*(y3-y4))/(x4-x3);
    // }
    // return ret;
    Vector dd=B-A;
    double d1=fabs(cross((a-A),dd)),d2=fabs(cross((b-A),dd));
    return a+(b-a)*(d1/(d1+d2));
}
Polygon convex_cut(Polygon g,Point a,Point b)
{
    Polygon ret; int sz=g.size();
    for(int i=0;i<sz;i++)
    {
        Point A=g[i],B=g[(i+1)%sz];
        if(ccw(a,b,A)!=-1) ret.pb(A);
        if(ccw(a,b,A)*ccw(a,b,B)==-1) ret.pb(cal_cross_point(a,b,A,B));
    }
    return ret;
}
double cal_area(Polygon g)
{
    int sz=g.size(); double ret=0;
    for(int i=0;i<sz;i++) ret+=cross(g[i],g[(i+1)%sz]);
    return abs(ret)/2.0;
}
double point_dis_line(Point a,Point b,Point p)
{
  return abs(cross(b-a,p-a)/(b-a).length());
}
double point_dis_seg(Point a,Point b,Point p)
{
  if(dot(b-a,p-a)<0.0) return (p-a).length();
  if(dot(a-b,p-b)<0.0) return (p-b).length();
  return point_dis_line(a,b,p);
}
double seg_dis_seg(Point a,Point b,Point c,Point d)
{
  if(intersect(a,b,c,d)) return 0.0;
  return min(point_dis_seg(a,b,c),min(point_dis_seg(a,b,d),min(point_dis_seg(c,d,a),point_dis_seg(c,d,b))));
}
Point project(Point a,Point b,Point c)// a-b,c
{
  Vector d=b-a,e=c-a;
  double r=dot(d,e)/d.length();
  return a+d/d.length()*r;
}
Point reflect(Point a, Point b, Point c)// a-b,c
{
  return c+(project(a,b,c)-c)*2;
}
pair<Point,Point> line_circle(circle c,line l)
{
  Point p=project(l.a,l.b,c.p);
  Vector e=unit(l.b-l.a);
  double r=sqrt(c.r*c.r-pf((p-c.p).length()));
  return make_pair(p+e*r,p-e*r);
}
Vector polar(double r,double a){return Point(r*cos(a),r*sin(a));}
pair<Point,Point> circle_circle(circle c1,circle c2)
{
  double d=(c1.p-c2.p).length();
  double a=acos((pf(c1.r)+pf(d)-pf(c2.r))/2/c1.r/d);
  double t=(c2.p-c1.p).angle();
  return make_pair(c1.p+polar(c1.r,t+a),c1.p+polar(c1.r,t-a));
}
pair<Point,Point> qie_dian(circle c,Point p)
{
  double t=(c.p-p).angle();
  double a=asin(c.r/(c.p-p).length());
  double d=sqrt(pf((c.p-p).length())-pf(c.r));
  return make_pair(p+polar(d,t+a),p+polar(d,t-a));
}
void common_tangent(circle c1,circle c2) // with c1
{
   double dis=(c1.p-c2.p).length();
   double rdif=(c1.r-c2.r); // not fabs
   if(fabs(rdif)-dis>eps) return;
   double rsum=c1.r+c2.r;
   double phi=(c2.p-c1.p).angle(),alpha;
   vector<Point> ans; ans.clear();
   if(fabs(fabs(rdif)-dis)<eps)alpha=acos(rdif/dis),ans.pb(c1.p+polar(c1.r,phi+alpha));
   else if(rsum-dis>eps) alpha=acos(rdif/dis),ans.pb(c1.p+polar(c1.r,phi+alpha)),ans.pb(c1.p+polar(c1.r,phi-alpha));
   else if(fabs(rsum-dis)<eps) alpha=acos(rdif/dis),ans.pb(c1.p+polar(c1.r,phi)),ans.pb(c1.p+polar(c1.r,phi+alpha)),ans.pb(c1.p+polar(c1.r,phi-alpha));
   else
   {
      alpha=acos(rdif/dis);
      ans.pb(c1.p+polar(c1.r,phi+alpha)),ans.pb(c1.p+polar(c1.r,phi-alpha));
      alpha=acos(rsum/dis);
      ans.pb(c1.p+polar(c1.r,phi+alpha)),ans.pb(c1.p+polar(c1.r,phi-alpha));
   }
   sort(ans.begin(),ans.end(),[](Point a,Point b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;});
   for(auto e:ans) printf("%.10f %.10f\n",e.x,e.y);
   return;
}
vector<Point> c_p_a_2(circle c,Point a,Point b)
{
   pair<Point,Point> u=line_circle(c,line(a,b));
   vector<Point> v; v.clear();
   if(ccw(a,b,u.fi)==0) v.pb(u.fi);
   if(ccw(a,b,u.se)==0) v.pb(u.se);
   return v;
}
double getarg(Vector a,Vector b)
{
   double t=b.angle()-a.angle();
   if(t>pi) t-=2*pi; if(t<-pi) t+=2*pi;
   return t;
}
double c_p_a_1(circle c,Point a,Point b)
{
  Vector va=c.p-a,vb=c.p-b; 
  double A=va.length(),B=vb.length(),f=cross(va,vb),d=point_dis_seg(a,b,c.p);
  if(fabs(f)<=eps) return 0;
  if(A<c.r+eps&&B<c.r+eps) return f*0.5;
  double alpha=getarg(va,vb);
  if(d>c.r-eps) return 0.5*alpha*c.r*c.r;
  vector<Point> u=c_p_a_2(c,a,b);
  double ans=0; u.insert(u.begin(),a); u.pb(b);
  sort(u.begin(),u.end(),[](Point a,Point b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;});
  if(u[0]!=a) reverse(u.begin(),u.end());
  for(int i=0;i+1<(int)u.size();i++) ans+=c_p_a_1(c,u[i],u[i+1]);
  return ans;
}
double circle_polygon_area(Polygon v,circle c)
{
  int n=v.size(); if(n<3) return 0;
  double ans=0;
  for(int i=0;i<n;i++)
  {
    Point a=v[i],b=v[(i+1)%n];
    ans+=c_p_a_1(c,a,b);
  }
  return ans;
}
int main()
{     
     int n; double r; cin>>n>>r;
     Polygon p;
     for(int i=1;i<=n;i++)
     {
       double x,y; cin>>x>>y;
       p.pb(Point(x,y));
     }
     printf("%.10f\n",circle_polygon_area(p,circle(Point(0,0),r)));
return 0;   
}
/*
*/