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 <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
namespace Random_Number{
	unsigned int seed = 19260817;
	void srnd(unsigned int x){ seed = x; }
	unsigned int rnd(){
		return seed ^= seed << 19, seed ^= seed >> 7, seed ^= seed << 1;
	}
}
using namespace Random_Number;
namespace Geometry{
	const double eps = 1e-9, pi = 3.14159265358979323846;
	bool equal(double a, double b){ return fabs(a - b) < eps; }
	struct point{
		double x, y;
		point(){}
		point(double _x, double _y){ x = _x, y = _y; }
		point operator * (const double &la) const { return point(x * la, y * la); }
		point operator / (const double &la) const { return point(x / la, y / la); }
		point operator + (const point &rhs) const { return point(x + rhs.x, y + rhs.y); }
		point operator - (const point &rhs) const { return point(x - rhs.x, y - rhs.y); }
		bool operator < (const point &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); }
		bool operator > (const point &rhs) const { return x > rhs.x || (x == rhs.x && y > rhs.y); }
		bool operator == (const point &rhs) const { return equal(x, rhs.x) && equal(y, rhs.y); }
		double len2() const { return x * x + y * y; }
		double len() const { return sqrt(len2()); }
		point unit() const { return *this / len(); }
		point unit2() const { return *this / len2(); }
		friend double distance(point a, point b){ return (a - b).len(); }
		friend double distance2(point a, point b){ return (a - b).len2(); }
		friend double dot(const point &a, const point &b){ return a.x * b.x + a.y * b.y; }
		friend double cross(const point &a, const point &b){ return a.x * b.y - a.y * b.x; }
		void read(){ scanf("%lf%lf", &x, &y); }
		void print(char ch = '\n') const { printf("%.10lf %.10lf", x, y), putchar(ch); }
		point rotation(double th) const { return point(x * cos(th) - y * sin(th), y * cos(th) + x * sin(th)); }
		friend double angle(const point &a, const point &b){ return atan2(cross(a, b), dot(a, b)); }
	};
	struct line{
		point a, b;
		line(){}
		line(point _a, point _b){ a = _a, b = _b; }
		void read(){ a.read(), b.read(); }
		void print(char ch1 = ' ', char ch2 = '\n') const { a.print(ch1), b.print(ch2); }
		point projection(const point &p) const { return a + (b - a).unit2() * dot(p - a, b - a); }
		point reflection(const point &p) const { return projection(p) * 2 - p; }
		int direction(const point &p) const {
			double t = cross(b - a, p - a);
			if (t >= eps) return 1;
			if (t <= -eps) return 2;
			double l1 = dot(p - a, b - a), l2 = dot(b - a, b - a);
			if (l1 <= -eps) return 3;
			if (l1 > l2) return 4;
			return 5;
		}
		friend bool parallel(const line &a, const line &b){ return equal(cross(a.b - a.a, b.b - b.a), 0); }
		friend bool orthogonal(const line &a, const line &b){ return equal(dot(a.b - a.a, b.b - b.a), 0); }
		friend std :: vector<point> cross_line(const line &a, const line &b){
			// gugugu
			return {};
		}
		friend bool segment_intersection(const line &a, const line &b){
			if (std :: min(a.a.x, a.b.x) >= std :: max(b.a.x, b.b.x) + eps) return 0;
			if (std :: min(b.a.x, b.b.x) >= std :: max(a.a.x, a.b.x) + eps) return 0;
			if (std :: min(a.a.y, a.b.y) >= std :: max(b.a.y, b.b.y) + eps) return 0;
			if (std :: min(b.a.y, b.b.y) >= std :: max(a.a.y, a.b.y) + eps) return 0;
			double t1, t2;
			t1 = cross(b.a - a.a, a.b - a.a), t2 = cross(b.b - a.a, a.b - a.a);
			if ((t1 >= eps && t2 >= eps) || (t1 <= -eps && t2 <= -eps)) return 0;
			t1 = cross(a.a - b.a, b.b - b.a), t2 = cross(a.b - b.a, b.b - b.a);
			if ((t1 >= eps && t2 >= eps) || (t1 <= -eps && t2 <= -eps)) return 0;
			return 1;
		}
		friend double distance_ps(const point &p, const line &l){
			double l1 = dot(p - l.a, l.b - l.a), l2 = dot(l.b - l.a, l.b - l.a);
			if (l1 > l2) return distance(p, l.b);
			if (l1 < 0) return distance(p, l.a);
			return fabs(cross(l.b - l.a, p - l.a)) / distance(l.a, l.b);
		}
		friend double distance_ss(const line &a, const line &b){
			if (segment_intersection(a, b)) return 0;
			return std :: min(std :: min(distance_ps(a.a, b), distance_ps(a.b, b)), 
			std :: min(distance_ps(b.a, a), distance_ps(b.b, a)));
		}
	};
	struct polygon{
		std :: vector<point> g;
		polygon(){}
		polygon(int n){ g.resize(n); }
		polygon(const std :: vector<point> &_g){ g = _g; }
		void clear(){ g.clear(); }
		void resize(int n){ g.resize(n); }
		int size() const { return g.size(); }
		void push_back(point x){ return g.push_back(x); }
		void pop_back(){ g.pop_back(); }
		point& operator [] (int x){ return g[x]; }
		const point& operator [] (int x) const { return g[x]; }
		double directed_area() const {
			int n = g.size();
			double s = 0;
			for (register int i = 0; i < n; ++i) s += cross(g[i], g[(i + 1) % n]);
			return s / 2;
		}
		bool is_convex() const {
			int n = g.size();
			for (register int i = 0; i < n; ++i)
				if (cross(g[(i + 1) % n] - g[i], g[(i - 1 + n) % n] - g[i]) <= -eps) return 0;
			return 1;
		}
		int polygon_point_containment(const point &a) const {
			double k = sqrt(1.0 * rnd() / rnd());
			line l = line(a, point(a.x + 1e9, a.y + 1e9 * k));
			int n = g.size(), s = 0;
			for (register int i = 0; i < n - 1; ++i)
				if (line(g[i], g[i + 1]).direction(a) == 5) return 1;
			if (line(g[n - 1], g[0]).direction(a) == 5) return 1;
			for (register int i = 0; i < n - 1; ++i)
				if (segment_intersection(l, line(g[i], g[i + 1]))) ++s;
			if (segment_intersection(l, line(g[n - 1], g[0]))) ++s;
			if (s & 1) return 2; else return 0;
		}
		void convex_hull(std :: vector<point> f){
			g.clear();
			int n = f.size();
			std :: sort(f.begin(), f.end());
			std :: vector<point> p;
			p.push_back(f[0]);
			for (register int i = 1; i < n; ++i){
				while (p.size() > 1 && cross(f[i] - p.back(), *(++p.rbegin()) - p.back()) <= -eps)
					p.pop_back();
				p.push_back(f[i]);
			}
			for (register int i = 0; i < p.size() - 1; ++i) g.push_back(p[i]);
			std :: reverse(f.begin(), f.end());
			p.clear(), p.push_back(f[0]);
			for (register int i = 1; i < n; ++i){
				while (p.size() > 1 && cross(f[i] - p.back(), *(++p.rbegin()) - p.back()) <= -eps)
					p.pop_back();
				p.push_back(f[i]);
			}
			for (register int i = 0; i < p.size() - 1; ++i) g.push_back(p[i]);
			f = g, n = f.size(), g.clear();
			int t = 0;
			for (register int i = 1; i < n; ++i)
				if (f[i].y < f[t].y || (f[i].y == f[t].y && f[i].x < f[t].x)) t = i;
			for (register int i = t; i < n; ++i) g.push_back(f[i]);
			for (register int i = 0; i < t; ++i) g.push_back(f[i]);
		}
		double convex_diamater() const {
			int n = g.size();
			double ans = 0;
			for (register int i = 0, j = 0; i < n; ++i){
				while (cross(g[i] - g[j], g[(i + 1) % n] - g[j])
				  < cross(g[i] - g[(j + 1) % n], g[(i + 1) % n] - g[(j + 1) % n]) + eps)
					j = (j + 1) % n;
				ans = std :: max(ans, distance(g[j], g[i]));
				ans = std :: max(ans, distance(g[j], g[(i + 1) % n]));
			}
			return ans;
		}
	};
	struct circle{
		point o;
		double r;
		circle(){}
		circle(point _o, double _r){ o = _o, r = _r; }
		void read(){ o.read(), scanf("%lf", &r); }
		void print(char ch = '\n') const { printf("%.10lf %.10lf %.10lf", o.x, o.y, r), putchar(ch); }
		int circle_intersection(const circle &c) const {
			double d = distance(o, c.o);
			if (d >= r + c.r + eps) return 4;
			if (equal(d, r + c.r)) return 3;
			if (d >= fabs(r - c.r) + eps) return 2;
			if (equal(d, fabs(r - c.r))) return 1;
			return 0;
		}
		std :: vector<point> directed_line_cross_point(const line &l) const {
			point p = line(l.a, l.b).projection(o), v = (l.b - l.a).unit();
			double d = distance(p, o);
			if (d >= r + eps) return {};
			double t = sqrt(r * r - (p - o).len2());
			if (equal(t, 0)) return {p};
			else return {p - v * t, p + v * t};
		}
		std :: vector<point> circle_cross_point(const circle &c) const {
			double d = distance(o, c.o);
			if (d <= fabs(r - c.r) - eps || d >= r + c.r + eps) return {};
			double x = (r * r - c.r * c.r + d * d) / (d * 2), h = sqrt(r * r - x * x);
			point p = (c.o - o).unit() * x, v = (c.o - o).unit().rotation(pi / 2) * h;
			if (v == point(0, 0)) return {p}; else return {p - v, p + v};
		}
		std :: vector<point> circle_point_tangent(const point &p) const {
			double d = distance(o, p);
			if (d <= r - eps) return {};
			if (equal(d, r)) return {p};
			return circle_cross_point(circle(p, sqrt(d * d - r * r)));
		}
		std :: vector<point> circle_common_tangent_out(const circle &c) const {
			if (equal(r, c.r)){
				point p = (c.o - o).unit().rotation(pi / 2) * r;
				return {o - p, o + p};
			}
			point p = (o * c.r - c.o * r) / (c.r - r);
			return circle_point_tangent(p);
		}
		std :: vector<point> circle_common_intangent_in(const circle &c) const {
			point p = (o * c.r + c.o * r) / (r + c.r);
			return circle_point_tangent(p);
		}
		double directed_triangle_intersection(const point &a, const point &b) const {
			bool ta = a.x * a.x + a.y * a.y < r * r + eps, tb = b.x * b.x + b.y * b.y < r * r + eps;
			std :: vector<point> t = circle(point(0, 0), r).directed_line_cross_point(line(b, a));
			if (ta == 1 && tb == 1) return cross(a, b) / 2;
			if (ta == 1 && tb == 0) return angle(t.front(), b) * r * r / 2 + cross(a, t.front()) / 2;
			if (ta == 0 && tb == 1) return angle(a, t.back()) * r * r / 2 + cross(t.back(), b) / 2;
			double s = angle(a, b) * r * r / 2;
			if (distance_ps(point(0, 0), line(a, b)) > r - eps) return s;
			return s + angle(t.front(), t.back()) * r * r / 2 - cross(t.front(), t.back()) / 2;
		}
		double directed_polygon_intersection(const polygon &g) const {
			int n = g.size();
			double s = 0;
			for (register int i = 0; i < n; ++i)
				s += directed_triangle_intersection(g[i] - o, g[(i + 1) % n] - o);
			return s;
		}
	};
}
using namespace Geometry;
int main(){
	int n;
	double r;
	scanf("%d%lf", &n, &r);
	polygon g(n);
	for (register int i = 0; i < n; ++i) g[i].read();
	printf("%.10lf\n", fabs(circle(point(0, 0), r).directed_polygon_intersection(g)));
}