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<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<ctime>
using namespace std;

typedef long long ll;

bool debug = false;
const int NIL = -1;
const int INF = 1000000000;
const int NUM = 100010;
const double eps = 1e-10;
const double PI = 3.1415926535897946;
clock_t START, END;

//basic defitition
struct Point {
	double x, y;
	Point(double x = 0, double y = 0) :x(x), y(y) {}
};
typedef Point Vector;
Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
Vector operator - (Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); }
Vector operator * (Vector A, double p) { return Vector(A.x * p, A.y * p); }
Vector operator / (Vector A, double p) { return Vector(A.x / p, A.y / p); }
bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
int dcmp(double x) { if (fabs(x) < eps)return 0; else return x < 0 ? -1 : 1; }
bool operator == (const Point& a, const Point& b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }
// basic operator
double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; }
double Length(Vector A) { return sqrt(Dot(A, A)); }
double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }
//point and line
double Distance(Point A, Point B) {
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
Point GetLineProjection(Point P, Point A, Point B) {
	Vector v = B - A;
	return A + v * (Dot(v, P - A) / Dot(v, v));
}
double DistanceToSegment(Point P, Point A, Point B) {
	if (A == B) return Length(P - A);
	Vector v1 = B - A, v2 = P - A, v3 = P - B;
	if (dcmp(Dot(v1, v2)) < 0) return Length(v2);
	else if (dcmp(Dot(v1, v3)) > 0) return Length(v3);
	else return fabs(Cross(v1, v2)) / Length(v1);
}
struct Circle {
	Point c;
	double r;
	Circle(Point c, double r) :c(c), r(r) {}
	Point point(double a) {
		return Point(c.x + cos(a) * r, c.y + sin(a) * r);
	}
};
Point GetOne(Circle O, Point A, Point B) {
	Point S = GetLineProjection(O.c, A, B);
	Vector v = (B - A) / Length(B - A);
	double L = sqrt(O.r * O.r - Distance(O.c, S) * Distance(O.c, S));
	Point C = S + v * L, D = S - v * L;
	if (dcmp(Dot(C - A, C - B)) <= 0)
		return C;
	else
		return D;
}
void GetTwo(Circle O, Point A, Point B, Point& P, Point& Q) {
	Point S = GetLineProjection(O.c, A, B);
	Vector v = (B - A) / Length(B - A);
	double L = sqrt(O.r * O.r - Distance(O.c, S) * Distance(O.c, S));
	P = S + v * L;
	Q = S - v * L;
}
double SectorArea(Point A, Point B, double r) {
	if (A == B)
		return 0;
	Point O(0, 0);
	double ang = acos(Dot(A - O, B - O) / r / r);
	return ang * r * r / 2;
}

int main(void)
{
	if (debug) {
		START = clock();
		freopen("in29.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	};
	int n, u = -1, v = -1, cnt_i = 0, cnt_o = 0;
	double x, y, _ans = 0, r;
	vector<Point> polygon, sol;
	Point O, X, Y;
	O.x = O.y = 0;
	scanf("%d%lf", &n, &r);
	Circle OO(O, r);
	for (int i = 0; i < n; i++) {
		scanf("%lf%lf", &x, &y);
		polygon.push_back(Point(x, y));
	}
	polygon.push_back(polygon[0]);
	for (int i = 0; i < n; i++) {
		double dis_u = Distance(Point(0, 0), polygon[i]);
		double dis_v = Distance(Point(0, 0), polygon[i + 1]);
		if (dcmp(dis_u - r) <= 0 && dcmp(dis_v - r) <= 0) {
			_ans += Cross(polygon[i] - O, polygon[i + 1] - O) / 2;
		}
		else if (dcmp(dis_u - r) > 0 && dcmp(dis_v - r) > 0) {
			double dist = fabs(Cross(polygon[i] - O, polygon[i + 1] - O) / Length(polygon[i + 1] - polygon[i]));
			if (dcmp(dist - r) >= 0) {
				X = GetOne(OO, O, polygon[i]);
				Y = GetOne(OO, O, polygon[i + 1]);
				if (dcmp(Cross(polygon[i + 1] - polygon[i], O - polygon[i])) > 0)
					_ans += SectorArea(X, Y, r);
				else
					_ans -= SectorArea(X, Y, r);
			}
			else {
				Point P, Q;
				GetTwo(OO, polygon[i + 1], polygon[i], P, Q);
				int t1 = dcmp(Dot(polygon[i + 1] - P, polygon[i] - P));
				int t2 = dcmp(Dot(polygon[i + 1] - Q, polygon[i] - Q));
				X = GetOne(OO, O, polygon[i]);
				Y = GetOne(OO, O, polygon[i + 1]);
				if (t1 >= 0 && t2 >= 0) {
					if (dcmp(Cross(polygon[i + 1] - polygon[i], O - polygon[i])) > 0)
						_ans += SectorArea(X, Y, r);
					else
						_ans -= SectorArea(X, Y, r);
				}
				else {
					if (dcmp(Length(X - Q) - Length(X - P)) < 0)
						swap(P, Q);
					if (dcmp(Cross(polygon[i + 1] - polygon[i], O - polygon[i])) > 0)
						_ans += SectorArea(X, P, r) + SectorArea(Y, Q, r) + dist * Length(P - Q) / 2;
					else
						_ans -= (SectorArea(X, P, r) + SectorArea(Y, Q, r) + dist * Length(P - Q) / 2);
				}
			}
		}
		else {
			if (dcmp(dis_u - r) <= 0) {
				X = GetOne(OO, polygon[i], polygon[i + 1]);
				_ans += Cross(polygon[i] - O, X - O) / 2;
				Y = GetOne(OO, O, polygon[i + 1]);
			}
			else {
				X = GetOne(OO, polygon[i + 1], polygon[i]);
				_ans += Cross(X - O, polygon[i + 1] - O) / 2;
				Y = GetOne(OO, O, polygon[i]);
			}
			if (dcmp(Cross(polygon[i + 1] - polygon[i], Y - polygon[i])) < 0)
				_ans -= SectorArea(X, Y, r);
			else
				_ans += SectorArea(X, Y, r);
		}
	}
	printf("%.10lf\n", _ans);
	if (debug) {
		END = clock();
		double endtime = (double)(END - START) / 1000;
		printf("total time = %lf s", endtime);
	}
	return 0;
}