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



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


//untested
//Area of polygon and circle intersection
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]);
		if (p[j]==p[i]) continue;
		assert(p[j]!=p[i]);
		Pt a=(p[i]-c.c)*v,b=(p[j]-c.c)*v;
		double d=norm(c.r)-norm(a.y);
		//cerr << a << ' ' << b << ' ' << sqrt(d) << endl;
		if (abs(a.y)<EPS/*deq(a.y,0)*/) continue;
		if (d<0) d=0;//r+=norm(c.r)*(arg(b)-arg(a));
		//else {
			d=sqrt(d);
			//cerr << d << endl;
			double l,m;
			r+=norm(c.r)*((l=atan2(b.y,min(b.x,-d))-atan2(a.y,min(a.x,-d)))
					+(m=atan2(b.y,max(b.x,d))-atan2(a.y,max(a.x,d))))
				+a.y*(min(d,max(a.x,-d))-max(-d,min(b.x,d)));
			assert(-pi < l && -pi<m && l<pi && m<pi);
			//cerr << "r: " << r << endl;
		//}
	}
	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();
	//cerr << distfinitelinept({10,-6},{-8,9},0) << endl;
}