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;

typedef long long ll;

// Can't use x and y for first and second
#define x real()
#define y imag()
#define X first
#define Y second
#define cpt const Pt&
//#define Pt Pt//const Pt&

//#define double long double
const double EPS = 1e-9;
const double pi=acos(-1);
bool deq(double a,double b) {return abs(a-b)<EPS;}
enum Orientation {CCW, CW, CNEITHER};

typedef complex<double> cpx;

struct Pt : public cpx {
    Pt() = default;
	using cpx::cpx;
	Pt(cpx a) : cpx(a) {}
    double& x const {
        return (double&)*this;
    }
    double& y const {
        return ((double*)this)[1];
    }

	bool operator ==(cpt b) const {return abs(*this-b) < EPS; }
	//by x first then break ties with y
	bool operator <(cpt b) const {return x<b.x || (x==b.x && y<b.y); }

	// Compare by arg then by norm (approximate)
	// arg is in range (-pi,pi].
	// Compare by arg then by norm (exact)
};

//Allow points to be read in by input streams
istream& operator >>(istream& is, Pt& p) {
	return is >> p.x >> p.y;
}

double dot(cpt a, cpt b) {return (conj(a) * b).x;}// Dot product
double det(cpt a, cpt b) {return (conj(a) * b).y;}//Determinant/"Cross Product"
double angle(cpt a, cpt b) {return arg(b - a);}// [-pi,pi] a to b with x axis
double angle (cpt a, cpt b, cpt c) {return arg((a-b)/(c-b));}//[-pi,pi]
//double slope(cpt a, cpt b) {return tan(arg(b - a));}// m for line segment (a,b)
double slope(cpt a, cpt b) {return (b.y-a.y)/(b.x-a.x);}

Pt rotate(cpt a, double theta) {return a * polar((double)1.0, theta);}//anticlockwise
//around p by theta anticlockwise
Pt rotate(cpt a, cpt p, double theta) {return rotate(a - p,theta) + p;}
Pt project(cpt p, cpt v) {return v * dot(p, v) / norm(v);}// p onto v
Pt project(cpt p, cpt a, cpt b) {return a+project(p-a,b-a);}//p onto line (a,b)
//reflect p across the line (a,b)
Pt reflect(cpt p, cpt a, cpt b) {return a + conj((p - a) / (b - a)) * (b - a);}

//bool colinear(Pt a, Pt b, Pt c) {return deq(det(b-a,c-b),0);}

// Orientation test (1 anticlockwise, -1 clockwise, 0 colinear)
int orient(cpt a, cpt b, cpt c) {
	double d=det(b-a,c-b);
	return d>EPS?1:d<-EPS?-1:0;
}

//Compare points by principal argument (-pi,pi] breaking ties by norm.
//0 is considered less than everything else.
//untested
bool argcompapprox(cpt a,cpt b) {
	if (b==0) return 0;
	if (a==0) return 1;
	double a1=arg(a),a2=arg(b);
	if (a1<-pi+EPS/2) a1+=2*pi;
	if (a2<-pi+EPS/2) a2+=2*pi;
	return a1+EPS<a2 || (deq(a1,a2) && norm(a)<norm(b));
}

//untested
bool argcompexact(cpt a,cpt b) {
	if (b==0) return 0;
	if (a==0) return 1;
	bool r1=a.y>0 || (a.y==0 && a.x<0);
	bool r2=b.y>0 || (b.y==0 && b.x<0);
	ll d=det(a,b);
	return r1<r2 || (r1==r2 && (d>0 || (d==0 && norm(a)<norm(b))));
}

// Point on line segment (including endpoints)
bool ptonseg(cpt a, cpt b, cpt p) {
	Pt u=b-a,v=p-a;
	return a==p || b==p ||
		((0 < dot(u,v) && dot(u,v) < norm(u)) && deq(det(u,v),0));
}

// Signed area of polygon
// Positive for anticlockwise orientation
double polygonarea(const vector<Pt>& p) {
	double r=0;
	int n=p.size();
	for (int j=0,i=n-1;j<n;i=j++) r+=det(p[i],p[j]);
	return r/2;
}

// Convex hull O(NlogN)
// if all points are colinear the middle points come up twice forwards and
// backwards e.g. a-b-c-d becomes a-b-c-d-c-b
// To remove colinear points change <-EPS and >EPS to <EPS and >-EPS.
vector<Pt> convexhull(vector<Pt> p) {
  sort(p.begin(),p.end()); p.resize(unique(p.begin(),p.end())-p.begin());
  int l=0,u=0;
  vector<Pt> L(p),U(p);
  if (p.size()<=2) return p;
  for (Pt& i:p) {
    while (l>1 && det(i-L[l-1],L[l-2]-i)<-EPS) l--;
    while (u>1 && det(i-U[u-1],U[u-2]-i)>EPS) u--;
    L[l++]=U[u++]=i;
  }
  L.resize(l+u-2);
  copy(U.rend()-u+1,U.rend()-1,L.begin()+l);

  return L;
}

//Point in polygon test O(N)
//Returns:
// 0 if not in polygon
// 1 if on boundary
// 2 if in interior
int ptinpoly(const vector<Pt>& p, cpt q) {
	int n=p.size();
	int i,j,r=0;
	for (j=0,i=n-1;j<n;i=j++) { //that trick to avoid modding
		if (ptonseg(p[i],p[j],q)) return 1;
		if (((p[i].y <= q.y && q.y < p[j].y)
			|| (p[j].y <= q.y && q.y < p[i].y))
			&& q.x < (p[j].x-p[i].x) * (q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
			r^=2;
	}
	return r;
}

Pt solve(cpt a, cpt b, cpt v) {// solves [a b]x==v with Cramer's rule.
	return Pt(det(v,b)/det(a,b),det(a,v)/det(a,b));
}

//Intersection of 2 line segments. Divides by 0 if they are parallel.
//Returns {nan,nan} if they don't intersect.
//Uncomment if statements below to get infinite lines.
Pt intersectline(Pt a, Pt b, Pt p, Pt q) {
	Pt ab=b-a,qp=p-q,ap=p-a;
	double s=det(ap,qp)/det(ab,qp),t=det(ab,ap)/det(ab,qp);
	//double s,t;
	//tie(s,t)=solve(b-a,p-q,p-a);
	//a+t(b-a)=p+s(q-p)
	
	//Can also just use ptonseg.
	if (-EPS<s && s<1+EPS //Answer is on ab
		&& -EPS<t && t<1+EPS) //Answer is on pq 
		return a+s*ab;
	return Pt(NAN,NAN);
}

//Distance between infinite line and point.
double distlinept(cpt a, cpt b, cpt p) {
	return abs(det(b-a,p-a)/abs(b-a));
}

//Distance between finite line and point
double distfinitelinept(Pt a, Pt b, Pt p) {
	b-=a;p-=a;
	double sp=(p/b).x;//dot(b,p)/norm(b);
	Pt closest;
	if (sp>=0) {
		if (sp>1) closest=b;
		else closest=sp*b;
	}
	return abs(closest-p); // Note that actual closest Pt on line is closest + a
}

//Are lines perpendicular
bool areperp(cpt a,cpt b,cpt p,cpt q) {
	return deq(dot(b-a,q-p),0);
}

//Are lines parallel?
bool arepara(cpt a, cpt b, cpt p, cpt q) {
	return deq(det(b-a,q-p),0);
}

//Distance between 2 finite lines
double distfinitelineline(cpt a,cpt b,cpt p,cpt q) {
	if (!arepara(a,b,p,q) && !std::isnan(intersectline(a,b,p,q).x)) return 0;
	
	/*if (arepara(a,b,p,q)) {
		b-=a;p-=a;q-=a;
		double sp=dot(b,p)/norm(b);
		if (0<sp && sp<1) return det(b,p)/abs(b);
	}*/
	
	return min({
			distfinitelinept(a,b,p),
			distfinitelinept(a,b,q),
			distfinitelinept(p,q,a),
			distfinitelinept(p,q,b)
	});
}

//This is kind of unnecessary
double distpara(Pt a, Pt b, Pt p, Pt q) {
	return distlinept(a,b,p);
}

struct Circle {
	Pt c;double r;
	bool operator==(const Circle& b) const {return c==b.c && deq(r,b.r);}
};

// Number of intersections, pair containing intersections
// 3 means infinitely many intersections. This also happens with identical
// radius 0 circles.
pair<int,pair<Pt,Pt>> intersectcirclecircle(const Circle& a,const Circle& b) {
	Pt v=b.c-a.c;
	//  disjoint           || one inside other
	if (a.r+b.r+EPS<abs(v) || abs(a.r-b.r)>abs(v)+EPS) return {0,{}};
	if (abs(v)<EPS) return {3,{}};
	double X=(norm(a.r)-norm(b.r)+norm(v))/(2.0*abs(v));
	double Ysq=norm(a.r)-norm(X),Y;
	v/=abs(v);
	if (Ysq<0 || (Y=sqrt(Ysq))<EPS) return {1,{Pt{X,0}*v+a.c,{}}};
	return {2,{Pt{X,Y}*v+a.c,Pt{X,-Y}*v+a.c}};
}

//untested
pair<int,pair<Pt,Pt>> intersectfinitelinecircle(cpt a,cpt b,Circle c) {
	Pt v=b-a;
	v/=abs(v);
	c.c=(c.c-a)/v;
	if (c.r+EPS<abs(c.c.y)) return {0,{}};
	double offsq=norm(c.r)-norm(c.c.y),off;
	if (offsq<0 || (off=sqrt(offsq))<EPS) {
		if (-EPS<c.c.x && c.c.x<abs(v)+EPS) return {1,{Pt{c.c.x,0}*v+a,{}}};
	}
	// Section much shorter without bounds check
	pair<int,pair<Pt,Pt>> ans;
	for (int sgn=-1;sgn<2;sgn+=2) {
		double X=c.c.x+sgn*off;
		if (-EPS<X && X<abs(v)+EPS) { // line bounds check
			if (ans.X==0) ans.Y.X=Pt{X,0}*v+a;
			else ans.Y.Y=Pt{X,0}*v+a;
			ans.X++;
		}
	}
	return ans;
}

//untested
Circle circlefrom3points(cpt a,cpt b,cpt c) {
	Pt v=b-a;
	// Circle not unique or infinite if points are colinear
	if (deq(det(v,c-a),0)) return {Pt(),-1};
	double X=abs(v);
	v/=abs(v);
	Pt p=(c-a)/v;
	Pt q(X/2,(norm(p.x)-norm(p.y)-p.x*X)/(2*p.y));
	return {q*v+a,abs(q)};
}

template<class T,int maxn>
struct Arr {
	int n=0;
	T a[maxn]={};
};

// Up to 4 common tangents for two circles (except when infinitely many). Each
// tangent is two points in Arr.
// 
// These points represent where the tangent touches each circle. If these points
// are the same then the second point is to the right of the first (when looking
// from the center of the first circle), and the distance between the two points
// is the distance between the centers of the circles.
// 
// Outer tangents are before inner tangents since they occur whenever inner
// tangents do. The first tangent in each group is the one which intersects the
// first circle to the left of the second circle (when looking from the center
// of the first circle).
//
// The radii should be positive. 0 radii should work but give multiple identical
// lines.
Arr<Pt,8> commontangents(const Circle& a,const Circle& b) {
	Arr<Pt,8> ans;
	if (a==b) {ans.n=9; return ans;} // infinitely many
	Pt v=b.c-a.c;
	double X=abs(v);
	v/=norm(X);
	int &n=ans.n;
	//Pt *aa=ans.a;
	for (int sgn=-1;sgn<2;sgn+=2) {
		Pt u=a.r+sgn*b.r;
		if (X+EPS<abs(u.x)) break;
		u.y=norm(X)-norm(u.x);
		if (u.y>=0) u.y=sqrt(u.y);

		ans.a[n++]=a.r*u;
		ans.a[n++]=(a.r+(u.y<EPS?X:u.y)*Pt(0,-1))*u;
		if (u.y>=EPS) {
			ans.a[n++]=a.r*conj(u);
			ans.a[n++]=(a.r-u.y*Pt(0,-1))*conj(u);
		}
	}

	for (int i=0;i<n;i++) ans.a[i]=ans.a[i]*v+a.c;

	return ans;
}

//Signed Area of polygon and circle intersection. Sign is determined by
//orientation of polygon. Divides by 0 if adjacent points are identical.
double areapolygoncircle(vector<Pt> p,Circle c) {
	int n=p.size();
	double r=0;
	for (int i=n-1,j=0;j<n;i=j++) {
		Pt v=abs(p[j]-p[i])/(p[j]-p[i]);
		Pt a=(p[i]-c.c)*v,b=(p[j]-c.c)*v;
		if (deq(a.y,0)) continue;
		double d=norm(c.r)-norm(a.y);
		if (d<0) d=0;
		d=sqrt(d);
		r+=norm(c.r)*(atan2(b.y,min(b.x,-d))-atan2(a.y,min(a.x,-d))
				+atan2(b.y,max(b.x,d))-atan2(a.y,max(a.x,d)))
			+a.y*(min(max(a.x,-d),d)-min(max(b.x,-d),d));
	}
	return r/2;
}

namespace AIZU_CGL_7_H {
	void solve() {
		int n,r;
		cin >> n >> r;
		vector<Pt> p(n);
		for (Pt &a:p) cin >> a;
		cout << fixed << setprecision(10) << areapolygoncircle(p,{0,(double)r}) << endl;
	}
}

int main() {
	
	//Test::solve();
	//UVA_920::solve();
	//UVA_10263::solve();
	//UVA_10927::solve(); // Use EPS=1e-10
	//UVA_378::solve();
	//UVA_191::solve();
	//AIZU_CGL_3_C::solve();
	//UVA_634::solve();
	//UVA_453::solve(); // Use EPS=1e-4
	AIZU_CGL_7_H::solve();
	//CirclePolyTest::solve();
}