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>
#define eps 1e-9
#define nmax 200
#define f(c,a,b) for(int c=a; c<=b; c++)
#define pi acos(-1)

using namespace std;
typedef double db;
struct P{
    db x, y;
    P operator - (P a){ return (P){x-a.x, y-a.y}; }
    db dot(P a){ return a.x*x + a.y*y; }
    P operator * (db a) { return (P){a*x, a*y}; }
    P operator + (P a){ return (P){x+a.x, y+a.y}; }
    P operator / (db a) { return (P) {x/a, y/a}; }
    db times(P a){ return x*a.y-y*a.x; }
    db le() { return sqrt( x*x+y*y ); }
    db le2() { return x*x+y*y; }
    P rot90(){ return (P){-y,x}; }
    db rad(P a) { return atan2(times(a),dot(a)); }
    void pri(){ printf("%.10lf %.10lf\n", x, y); }
    void swap(P& a){
        db tx = x, ty = y;
        x = a.x;  y = a.y;
        a.x = tx; a.y = ty;
    }
    bool operator < (const P a) const { return (x==a.x)?(y<a.y):(x<a.x); } 
    bool operator == (const P a) const { return (x==a.x)&&(y==a.y); }
}po[nmax];

int sign(db x) { return (x<-eps) ? -1 : x>eps; }
db disLP(P p1, P p2, P p){ return abs( (p1-p).times(p2-p) ) / (p1-p2).le(); }

P projection(P a, P p, P q){ 
    P tl = q - p; 
    db ll = tl.le();  
    db k = (a-p).dot(tl)/ll/ll;  
    return (P){ p.x + k*tl.x, p.y + k*tl.y }; 
}

db disSP(P p1, P p2, P p){
    if((p1-p2).dot(p-p2) < eps) return (p-p2).le();
    if((p2-p1).dot(p-p1) < eps) return (p-p1).le();
    return disLP(p1, p2, p);
}

vector<P> cpCL(P c1, db r1, P p1, P q1){ 
    db dis = disLP(p1, q1, c1);
    dis = sqrt( r1*r1-dis*dis );
    P pj = projection(c1, p1, q1);
    P a1 = pj + (p1-q1) /(p1-q1).le() *dis;
    P a2 = pj + (q1-p1) /(q1-p1).le() *dis;
    return {a1, a2};
}

db interCT(P p1, db r1, P p2, P p3){
    P tp=p1; p1=p1-p1; p2=p2-tp; p3=p3-tp;
    int pd2 = sign(r1*r1-p2.le2()), pd3 = sign(r1*r1-p3.le2());
    vector <P> cp = cpCL(p1, r1, p2, p3);
    if(pd2>=0){
        if(pd3>=0) return p2.times(p3);
        return p2.times(cp[1]) + r1*r1*cp[1].rad(p3);
    }else{
        if(pd3>=0) return cp[0].times(p3) + r1*r1*p2.rad(cp[0]);
        if(disSP(p2,p3,p1) >= r1) {  return r1*r1*p2.rad(p3); }
        return r1*r1*p2.rad(cp[0])+cp[0].times(cp[1])+r1*r1*cp[1].rad(p3);
    }
}

int main(){
    //freopen("owo.in","r",stdin);
    int n;
    db r, ans=0;
    cin >> n >> r;
    f(i,0,n-1) scanf("%lf%lf", &po[i].x, &po[i].y);
    f(i,0,n-1) {
        db test=interCT((P){0,0}, r, po[i], po[(i+1)%n]);
        ans += test;
    }
    printf("%.12lf\n", ans/2);
    return 0;
}