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;
const double eps=1e-7,pi=acos(-1.0);
struct dot{
	double x,y;
	double len(){return sqrt(x*x+y*y);}
	dot(double a=0.0,double b=0.0){x=a,y=b;}
	dot operator +(const dot&b)const {return dot(x+b.x,y+b.y);}
	dot operator -(const dot&b)const {return dot(x-b.x,y-b.y);}
	dot operator *(const double&z)const {return dot(x*z,y*z);}
	bool operator <(const dot&b)const {return (y<b.y)||(y==b.y&&x<b.x);}
	bool operator >(const dot&b)const {return (y>b.y)||(y==b.y&&x>b.x);}	
	bool operator ==(const dot&b)const {return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}	
	bool operator !=(const dot&b)const {return fabs(x-b.x)>=eps||fabs(y-b.y)>=eps;}
	void read(){scanf("%lf%lf",&x,&y);} 
};
struct line{
	dot x1,x2;
	void read(){x1.read();x2.read();};
	line(dot a=dot(0.0,0.0),dot b=dot(0.0,0.0)){x1=a,x2=b;} 
	dot getdot(){return x2-x1;}
};
double chaji(dot x,dot y){
	return x.x*y.y-x.y*y.x;
}
double neiji(dot x,dot y){
	return x.x*y.x+x.y*y.y;
}
double cos(dot x,dot y){
	if (!x.len()||!y.len())return 0;
	return neiji(x,y)/x.len()/y.len();
}
dot Projection(dot x,line y){//求x关于直线y的投影点（垂足） 
	y.x2=y.x2-y.x1;
	x=x-y.x1;
	double len=cos(x,y.x2)*x.len()/y.x2.len();
	y.x2=y.x2*len;
	return y.x2+y.x1;
}
dot Reflection(dot x,line y){//求x关于直线y的对称点 
	dot z=Projection(x,y);
	return z*2-x;
}
int Counter_Clockwise(dot x,line y){//求两个向量的五种关系 
	x=x-y.x1;y.x2=y.x2-y.x1;
	if (chaji(y.x2,x)!=0){
		if (chaji(y.x2,x)>0)return 1;
		return 2;
	} 
	if (fabs(cos(x,y.x2)+1)<eps)return 3;
	if (x.len()>y.x2.len())return 4;
	return 5;
} 
int Parallel_Orthogonal(line x,line y){//求两个直线是垂直还是平行还是其他 
	dot a=x.getdot(),b=y.getdot();
	if (chaji(a,b)==0)return 2;
	if (neiji(a,b)==0)return 1;
	return 0;
}
int Intersection(line x,line y){//求两条线段是否相交 
	int Minx1=min(x.x1.x,x.x2.x),Maxx1=max(x.x1.x,x.x2.x);
	int Minx2=min(y.x1.x,y.x2.x),Maxx2=max(y.x1.x,y.x2.x);
	int Miny1=min(x.x1.y,x.x2.y),Maxy1=max(x.x1.y,x.x2.y);
	int Miny2=min(y.x1.y,y.x2.y),Maxy2=max(y.x1.y,y.x2.y);
	if (Minx1>Maxx2||Minx2>Maxx1)return 0;
	if (Miny1>Maxy2||Miny2>Maxy1)return 0;
	if (chaji(x.getdot(),y.x1-x.x1)*chaji(x.getdot(),y.x2-x.x1)>0)return 0;
	if (chaji(y.getdot(),x.x1-y.x1)*chaji(y.getdot(),x.x2-y.x1)>0)return 0;
	return 1;
}
int Intersection2(line x,line y){//求线段和直线是否相交 
	if (chaji(y.getdot(),x.x1-y.x1)*chaji(y.getdot(),x.x2-y.x1)>0)return 0;
	return 1;
}
dot CrossPoint(line x,line y){//求两条线段的交点 
	if (fabs(cos(x.getdot(),y.getdot())-1)<eps||fabs(cos(x.getdot(),y.getdot())+1)<eps){
		if (x.x1<x.x2)swap(x.x1,x.x2);
		if (y.x1<y.x2)swap(y.x1,y.x2);
		if (x.x2<y.x2)return y.x2;
		else return x.x2;
	}
	else {
		if (x.x2.x-x.x1.x==0){
			double k2=(y.x2.y-y.x1.y)/(y.x2.x-y.x1.x),b2=y.x2.y-y.x2.x*k2;
			return dot(x.x2.x,x.x2.x*k2+b2);
		}
		if (y.x2.x-y.x1.x==0){
			double k1=(x.x2.y-x.x1.y)/(x.x2.x-x.x1.x),b1=x.x2.y-x.x2.x*k1;
			return dot(y.x2.x,y.x2.x*k1+b1);			
		}
		double k1=(x.x2.y-x.x1.y)/(x.x2.x-x.x1.x),b1=x.x2.y-x.x2.x*k1;
		double k2=(y.x2.y-y.x1.y)/(y.x2.x-y.x1.x),b2=y.x2.y-y.x2.x*k2;
		dot ans;
		ans.x=(b2-b1)/(k1-k2);ans.y=ans.x*k1+b1;
		return ans;
	}
} 
double Dis(dot x,dot y){//点到点的距离 
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double dist(line x,dot y){//点到线段的距离 
	dot P=Projection(y,x);
	double k=neiji(x.getdot(),P-x.x1)/neiji(x.getdot(),x.getdot());
	if (k<=0)return Dis(x.x1,y);
	if (k>=1)return Dis(x.x2,y);
	return Dis(y,P);
}
double Distance(line x,line y){//线段之间距离 
	return min(min(dist(x,y.x1),dist(x,y.x2)),min(dist(y,x.x1),dist(y,x.x2)));
}
struct polygon{
	vector<dot > A;
	double S(){//多边形面积
		double ans=0;
		for (int i=0;i+1<A.size();i++)ans+=chaji(A[i],A[i+1])/2;
		if (A.size()>1)ans+=chaji(A[A.size()-1],A[0])/2;
		return ans;		
	}
	double C(){//多边形周长 
		double ans=0;
		for (int i=0;i+1<A.size();i++)ans+=Dis(A[i],A[i+1]);
		if (A.size()>1)ans+=Dis(A[A.size()-1],A[0]);
		return ans;
	}
	void read(){
		int n;scanf("%d",&n);A.resize(n);
		for (int i=0;i<n;i++)A[i].read();
	}
	int Is_Convex(){//是否是凸多边形 
		for (int i=0;i<A.size();i++)
			if (chaji(A[(i+1)%A.size()]-A[i],A[(i+2)%A.size()]-A[(i+1)%A.size()])<0)
				return 0;
		return 1;
	}
}G;
int PolygonPointContainment(polygon G,dot x){//射线和多边形的关系
	for (int i=0;i<G.A.size();i++)
		if (Counter_Clockwise(x,line(G.A[i],G.A[(i+1)%G.A.size()]))==5)return 1;
	for (int i=0;i<G.A.size();i++)
		if (x==G.A[i])return 1;
	double k=sqrt(2)+1,b=x.y-x.x*k;
	dot x2=dot(-1000000000,-1000000000*k+b);line R=line(x,x2);
	int ans=0;
	for (int i=0;i<G.A.size();i++)
		if (Intersection(R,line(G.A[i],G.A[(i+1)%G.A.size()])))ans++;
	if (ans&1)return 2;
	return 0;	
}
int isclock(dot x,dot y,dot z){//是否顺时针 
	return chaji(z-x,y-x)<0;
}
polygon Convex_Hull(polygon G){//求凸包 
	polygon ans1,ans2;
	sort(G.A.begin(),G.A.end());
	ans1.A.push_back(G.A[0]);ans1.A.push_back(G.A[1]);
	for (int i=2;i<G.A.size();i++){
		while (ans1.A.size()>=2&&isclock(ans1.A[ans1.A.size()-2],ans1.A[ans1.A.size()-1],G.A[i]))
			ans1.A.pop_back();
		ans1.A.push_back(G.A[i]);	
	}
	ans2.A.push_back(G.A[G.A.size()-1]);ans2.A.push_back(G.A[G.A.size()-2]);
	for (int i=G.A.size()-3;i>=0;i--){
		while (ans2.A.size()>=2&&isclock(ans2.A[ans2.A.size()-2],ans2.A[ans2.A.size()-1],G.A[i]))
			ans2.A.pop_back();
		ans2.A.push_back(G.A[i]);		
	}
	for (int i=1;i<ans2.A.size()-1;i++)ans1.A.push_back(ans2.A[i]);
	return ans1;
}
double DiameterofaConvexPolygon(polygon G){//求直径 
	int l=0,r=1,flag=1;
	double ans=Dis(G.A[0],G.A[1]);
	while (l!=0||flag){
		flag=0;
		while (Dis(G.A[l],G.A[r])<=Dis(G.A[l],G.A[(r+1)%G.A.size()])){
			r=(r+1)%G.A.size();
			ans=max(ans,Dis(G.A[l],G.A[r]));
		}
		l=(l+1)%G.A.size();
		ans=max(ans,Dis(G.A[l],G.A[r]));
	}
	return ans;
}
double Convex_Cut(polygon G,line x){//求多边形在线的左边的部分 
	polygon ans;line y=x;
	for (int i=0;i<G.A.size();i++){
		if (chaji(y.x2-y.x1,G.A[i]-y.x1)>=0)ans.A.push_back(G.A[i]);
		if (Intersection2(line(G.A[i],G.A[(i+1)%G.A.size()]),y))
			ans.A.push_back(CrossPoint(line(G.A[i],G.A[(i+1)%G.A.size()]),y));	
	}
	return ans.S();
}
int cmp2(int x,int y){
	return G.A[x]<G.A[y];
}
double ClosestPair(int l,int r){//求平面最近点对 
    double d=1e20;vector<int > ans;
    if (l==r)return d;
    if (l+1==r)return Dis(G.A[l],G.A[r]);
    int mid=(l+r)/2; 
    double d1=ClosestPair(l,mid),d2=ClosestPair(mid+1,r);
    d=min(d1,d2);
    for (int i=l;i<=r;i++)
        if (fabs(G.A[mid].x-G.A[i].x)<=d)ans.push_back(i);
    sort(ans.begin(),ans.end(),cmp2);
    for (int i=0;i<ans.size();i++)
        for (int j=i+1;j<ans.size()&&G.A[ans[j]].y-G.A[ans[i]].y<d;j++)
			d=min(d,Dis(G.A[ans[i]],G.A[ans[j]]));
    return d;
}
int cmp(dot x,dot y){
	return x.x<y.x||(x.x==y.x&&x.y<y.y);
}
struct circle{
	dot x;
	int r;
	void read(){
		x.read();
		scanf("%d",&r);
	}
	circle(dot _x=dot(0,0),double _r=0.0){x=_x,r=_r;}
};
int IntersectionofCircles(circle x,circle y){//求两个圆的公切线个数 
	if (x.r+y.r<Dis(x.x,y.x))return 4;
	if (x.r+y.r==Dis(x.x,y.x))return 3;
	if (fabs(x.r-y.r)<Dis(x.x,y.x))return 2;
	if (fabs(x.r-y.r)==Dis(x.x,y.x))return 1;
	return 0;
}
line CrossPointsofaCirceandaLine(circle x,line y){//求圆和直线的交点 
	dot K=Projection(x.x,y);
	double p=sqrt(x.r*x.r-Dis(x.x,K)*Dis(x.x,K));
	line ans;y.x1=y.x1-K;y.x2=y.x2-K;
	ans.x1=(y.getdot())*(p/(y.getdot()).len())+K;
	ans.x2=(y.getdot())*(-p/(y.getdot()).len())+K;
	return ans;
}
double arg(dot x){
	return atan2(x.y,x.x);
}
dot polar(double x,double y){
	return dot(cos(y)*x,sin(y)*x);
}
line CrossPointsofCircles(circle x,circle y){//求两个圆的交点 
	line ans;
	double d=Dis(x.x,y.x);
	double a=acos((x.r*x.r+d*d-y.r*y.r)/(2*x.r*d));
	double t=arg(y.x-x.x);
	ans.x1=dot(x.x+polar(x.r,t+a));
	ans.x2=dot(x.x+polar(x.r,t-a));
	return ans;
}
line TangenttoaCircle(circle x,dot y){//求圆和线段的切点 
	line ans;
	double d=Dis(x.x,y);
	double a=acos(x.r/d);
	double t=arg(y-x.x);
	ans.x1=dot(x.x+polar(x.r,t+a));
	ans.x2=dot(x.x+polar(x.r,t-a));
	return ans;
}
polygon CommonTangent(circle x,circle y){//求两个圆的公切线 
	polygon ans;
	int flag=IntersectionofCircles(x,y);
	double t=arg(y.x-x.x);
	if (flag>=2){
		double d=Dis(x.x,y.x);
		double p=sqrt(d*d-(x.r-y.r)*(x.r-y.r)+y.r*y.r);
		double a=acos((x.r*x.r+d*d-p*p)/(2*x.r*d));
		ans.A.push_back(x.x+polar(x.r,t+a));
		ans.A.push_back(x.x+polar(x.r,t-a));
	}
	if (flag==4){
		double d=Dis(x.x,y.x);
		double p=sqrt(y.r*y.r+d*d-(x.r+y.r)*(x.r+y.r));
		double a=acos((x.r*x.r+d*d-p*p)/(2*x.r*d));
		ans.A.push_back(x.x+polar(x.r,t+a));
		ans.A.push_back(x.x+polar(x.r,t-a));
	}
	if (flag&1){
		line p=CrossPointsofCircles(x,y);
		ans.A.push_back(p.x1);
	}
	return ans;
}
double getS(line x,int r){ 
	double ans=0;line z=x;
	if (dist(x,dot(0,0))+eps>=r){
  		double tmp=neiji(x.x1,x.x2)/(x.x1.len()*x.x2.len());
  		if (tmp<-1.0)tmp=-1.0;
  		if (1.0<tmp)tmp=1.0;
  		double t=acos(tmp); 
		ans=fabs(r*r*t/2);
	}
	else if (Dis(dot(0,0),x.x1)<=r+eps&&Dis(dot(0,0),x.x2)<=r+eps)ans=fabs(chaji(x.x1,x.x2)/2);
	else {
		line y=CrossPointsofaCirceandaLine(circle(dot(0,0),r),x);
		if (x.x1>x.x2)swap(x.x1,x.x2);
		if (y.x1>y.x2)swap(y.x1,y.x2);
		int flag1=!(y.x1<x.x1)&&(x.x1!=y.x1),flag2=!(y.x2>x.x2)&&(x.x2!=y.x2);
		if (flag1)ans=fabs(getS(line(x.x1,y.x1),r))+fabs(getS(line(y.x1,x.x2),r));
		else ans=fabs(getS(line(x.x1,y.x2),r))+fabs(getS(line(y.x2,x.x2),r));
	}
	if (chaji(z.x1,z.x2)<0.0)ans=-ans;
	return ans;
}
double IntersectionofaCircleandaPolygon(polygon G,int r){//求多边形和圆面积的交 
	double ans=0.0;
	for (int i=0;i+1<G.A.size();i++)ans+=getS(line(G.A[i],G.A[i+1]),r);
	ans+=getS(line(G.A[G.A.size()-1],G.A[0]),r);
	return ans;
}
int main(){
	int r,n;polygon G;
	scanf("%d%d",&n,&r);
	G.A.resize(n);
	for (int i=0;i<n;i++)G.A[i].read();
	printf("%.10lf\n",IntersectionofaCircleandaPolygon(G,r));
	return 0;
}