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:
/*
幾何
https://gist.github.com/zeptometer/3719669
複素数平面による幾何ライブラリ←もっと短くなる可能生アリ
http://osrehun.hatenadiary.jp/entry/2016/12/31/145827

*/
#include <bits/stdc++.h>
using namespace std;

using DD=double;


#define EPS 1e-10
#define eq(a,b) (abs( (a) - (b) )<EPS)
const DD PI=acosl(-1.0);
constexpr DD INF=1LL<<62;

//点
using P=complex<DD>;
//ベクトル
using V=P;
//線分
struct Segment{
    P a,b;
    Segment()=default;
    Segment(P a,P b) :a(a),b(b){}
    Segment(DD ax,DD ay,DD bx,DD by):a(ax,ay),b(bx,by){}

};
//直線
using Line=Segment;
//円
struct Circle{
    P p;
    DD r;
    Circle()=default;
    Circle(P p,DD r):p(p),r(r){}
};
using Polygon=vector<P>;

//++++++++++++++++基本計算++++++++++++++//
inline DD torad(const DD &deg){return deg*PI/180;}
inline DD todeg(const DD &rad){return rad*180/PI;}
//内積
inline DD dot(const V &a,const V &b){
    return real(a*conj(b));
}
//外積
inline DD cross(const V &a,const V &b){
    return imag(conj(a)*b);
}
//ベクトルvを反時計回りにr度回転
inline V rotate(const V &v,const DD r){
    return v*V(cos(r),sin(r));
}
inline bool xy(const P &a,const P &b){
    if(real(a)+EPS<=real(b)) return true;
    if(eq(real(a),real(b)) && imag(a)+EPS<imag(b)) return true;
    return false;
}
inline bool yx(const P &a,const P &b){
    if(imag(a)+EPS<imag(b)) return true;
    if(eq(imag(a),imag(b)) && real(a)+EPS<real(b)) return true;
    return false;
}

//++++++++++++++++平行や直交+++++++++++++++//
inline bool isOrthogonal(const V &a,const V &b){
    return eq(dot(a,b),0.0);
}
inline bool isOrthogonal(const Segment &a,const Segment &b){
    return eq(dot(a.a-a.b,b.a-b.b),0);
}
inline bool isParallel(const V &a,const V &b){
    return eq(cross(a,b),0.0);
}
inline bool isParallel(const Segment &a,const Segment &b){
    return eq(cross(a.a-a.b,b.a-b.b),0);
}
//線分a-bに対してcがどの位置にあるか
//ccwの簡略版 反時計回り:1 時計回り:-1 直線上:0
inline int ccw(const P &a,const P &b,const P &c){
    DD cr=cross(b-a,c-a);
    if(cr>EPS) return 1;
    if(cr<-EPS) return -1;
    return 0;
}

//線分a-bに対してcがどの位置にあるか
//反時計回り:1　時計回り:-1 直線上(a,b,c:-2 a,c,b:0 c,a,b:2) 
inline int ccwH(P a,P b,P c){
    b-=a;c-=a;
    if(cross(b,c)>EPS) return 1;
    if(cross(b,c)<-EPS) return -1;
    if(dot(b,c)<-EPS) return 2;
    if(norm(b)<norm(c)) return -2;
    return 0;
}


//+++++++++++++++射影+++++++++++++++++++++//
inline P project(const P &p,const Segment &s){
    V base=s.b-s.a;
    DD r=dot(p-s.a,base)/norm(base);
    return s.a+base*r;
}
inline P reflect(const P &p,const Segment &s){
    return p+(project(p,s)-p)*2.0;
}
/*++++++++++点との距離++++++++++++++++++*/
//点と直線の距離
inline DD dis(const P &p,const Line &l){return abs(cross(l.b-l.a,p-l.a))/abs(l.b-l.a);}
//点と線分の距離
inline DD disPS(const P &p,const Segment &s){
    if( dot(s.b-s.a,p-s.a)<0.0 ) return abs(p-s.a);
    if( dot(s.a-s.b,p-s.b)<0.0 ) return abs(p-s.b);
    return dis(p,s); //点と直線の距離
}


//+++++++++++++++線分と直線+++++++++++++++++//

//線分a-b,c-dは交差するか?
inline bool intersect(const P &a,const P &b,const P &c,const P &d){
    return(ccwH(a,b,c)*ccwH(a,b,d)<=0 && ccwH(c,d,a)*ccwH(c,d,b)<=0);
}
//線分s,tは交差するか？
inline bool intersect(const Segment &s,const Segment &t){
    return intersect(s.a,s.b,t.a,t.b);
}
//線分と線分の交点
//これをやる前にintersectで判定
inline P crossPoint(const Segment &s,const Segment &t){
    V base=t.b-t.a;
    DD d1=abs(cross(base,s.a-t.a));
    DD d2=abs(cross(base,s.b-t.a));
    DD r=d1/(d1+d2);
    return s.a+(s.b-s.a)*r;
}
//線分と線分の距離
inline DD dis(const Segment &s,const Segment t){
    if(intersect(s,t)) return 0.0;
    return min(min(disPS(t.a,s),disPS(t.b,s)),min(disPS(s.a,t),disPS(s.b,t)) );
}

//+++++++++++円++++++++++++++++//

//円cと直線lの交点
//abs(l,c.p)<c.r+EPSが必要
pair<P,P> crossPoint(const Line &l,const Circle &c){
    P pr=project(c.p,l);
    V e=(l.b-l.a)/(abs(l.b-l.a));
    DD base=sqrt(c.r*c.r-norm(pr-c.p));
    return make_pair(pr+e*base,pr-e*base);
}
//線分sと円cの交点
vector<P> crossPointSC(const Segment &s,const Circle &c){
    vector<P> ret;
    if(dis(c.p,s)>=c.r+EPS) return ret;
    auto p=crossPoint(s,c);
    if(dot(p.first-s.a,s.b-s.a)>0 && dot(p.first-s.b,s.a-s.b)>0) ret.push_back(p.first);
    if(dot(p.second-s.a,s.b-s.a)>0 && dot(p.second-s.b,s.a-s.b)>0) ret.push_back(p.second);
    if(xy(s.a,s.b)) sort(ret.begin(),ret.end(),xy);
    else sort(ret.rbegin(),ret.rend(),xy);
    return ret;
}

//共通接線の数
//離れている:4 外接:3 交わる:2 内接:1 内包:0
inline int intersect(const Circle &a,const Circle &b){
    DD d=abs(a.p-b.p);
    if(d>a.r+b.r+EPS) return 4;
    if(eq(d,a.r+b.r)) return 3;
    if(eq(d,abs(a.r-b.r))) return 1;
    if(d<abs(a.r-b.r)-EPS) return 0;
    return 2;
}

//円c1と円c2の交点
//これを使う前に交点があるかどうかを判定する
vector<P> crossPoint(const Circle &a,const Circle &b){
    vector<P> ret;
    if(abs(a.p-b.p)>a.r+b.r+EPS) return ret;
    DD d=abs(a.p-b.p);
    DD s=acos((a.r*a.r+d*d-b.r*b.r)/(2*a.r*d));
    DD t=arg(b.p-a.p);
    if(eq(s,0)) ret.emplace_back(a.p+polar(a.r,t+s));
    else ret.push_back(a.p+polar(a.r,t+s)),ret.push_back(a.p+polar(a.r,t-s));
    return ret;
}

//pがcの外にあるかの判定が必要
vector<P> TanLine(const P &p,const Circle &c){
    vector<P> ret;
    DD d=abs(p-c.p);
    if(d<=c.r-EPS) return ret;
    if(eq(d,c.r)){
        ret.push_back(p);
        return ret;
    } 
    return crossPoint(c,Circle(p,sqrt(d*d-c.r*c.r)));
}
//https://ei1333.github.io/luzhiled/snippets/geometry/template.html
//↑すごい。丸写し
//円c1,c2の共通接線
//接点をつないで線にしている(１個だけ追加するときに注意)
vector<Line> TanLine(Circle a,Circle b){
    vector<Line> ret;
    if(a.r<b.r) swap(a,b);
    DD g=abs(a.p-b.p);
    if(eq(g,0)) return ret;
    V u=(b.p-a.p)/g;
    V v=rotate(u,PI*0.5);
    for(DD s:{-1,1}){
        DD h=(a.r+s*b.r)/g;
        if(eq(1-h*h,0)){
            ret.emplace_back(a.p+u*a.r,a.p+(u+v)*a.r);
        }else if(1-h*h>0){
            V uu=u*h,vv=v*sqrt(1-h*h);
            ret.emplace_back(a.p+(uu+vv)*a.r,b.p-(uu+vv)*b.r*s);
            ret.emplace_back(a.p+(uu-vv)*a.r,b.p-(uu-vv)*b.r*s);
        }
    }
    return ret;
}

/*+++++++++++++++++++三角形+++++++++++++++++*/
//外心
//isParallel()を使って判定を忘れずに
P circumcenter(const P &a,const P &b,const P &c){
    P ab=(a+b)/2.0,bc=(b+c)/2.0;
    Segment s(ab,ab+polar(1.0,arg(b-a)+PI*0.5));
    Segment t(bc,bc+polar(1.0,arg(c-b)+PI*0.5));
    return crossPoint(s,t);
}

/*+++++++++++++++++++多角形+++++++++++++++++++*/
//IN:2 ON:1 OUT:0
//点がどの位置にあるか
int contains(const P &p,const Polygon &g){
    int n=(int)g.size();
    bool x=false;
    for(int i=0;i<n;i++){
        V a=g[i]-p,b=g[(i+1)%n]-p;
        if(eq(cross(a,b),0) && dot(a,b)<EPS) return 1;
        if(imag(a)>imag(b)) swap(a,b);
        if(imag(a)<EPS && EPS<imag(b) && cross(a,b)>EPS) x=!x;
    }
    return (x?2:0);
}
//凸性判定
bool isConvex(const Polygon &g){
    int n=(int)g.size();
    int flag=0;
    int t;
    for(int i=0;i<n;i++){
        V a(g[(i+1)%n]-g[i]),b(g[(i+2)%n]-g[i]);
        if(cross(a,b)>EPS) t=1;
        else if(cross(a,b)<-EPS) t=-1;
        else continue;
        if(flag==-t) return false;
        flag=t;
    }
    return true;
}

//凸包　アンドリューのアルゴリズム
//https://github.com/drken1215/algorithm/blob/master/Geometry/All.cpp←螺旋本より早そう
//j=1:返上の点を含まない　j=-1:含む
//反時計回りの多角形を返す
//sはソートされる
Polygon ConvexHull(Polygon &s,const int j){
    int sz=(int)s.size();
    if(sz<3) return s;
    sort(s.begin(),s.end(),yx);

    int n=0;
    Polygon res(2*sz);
    for(int i=0;i<sz;i++){
        while(n>=2 && cross(res[n-1]-res[n-2],s[i]-res[n-2])<EPS*j){
            n--;
        }
        res[n]=s[i];
        n++;
    }
    int t=n+1;
    for(int i=sz-2;i>=0;i--){
        while(n>=t && cross(res[n-1]-res[n-2],s[i]-res[n-2])<EPS*j){
            n--;
        }
        res[n]=s[i];
        n++;
    }
    res.resize(n-1);
    return res;
}

//符号付き面積
//反時計回りの図形なら正
//https://imagingsolution.net/math/calc_n_point_area/
DD Area(const Polygon &g){
    DD ret=0.0;
    int n=(int)g.size();
    for(int i=0;i<n;i++){
        ret+=cross(g[i],g[(i+1)%n]);
    }
    return ret/2.0L;
}

//反時計回り
//理解が浅い←大体分かった（本当か？）
DD Diameter(Polygon g){
    g=ConvexHull(g,1);
    int gz=g.size();
    int m=0,M=0;
    for(int i=1;i<gz;i++){
        if(imag(g[i])<imag(g[m])) m=i;
        if(imag(g[i])>imag(g[M])) M=i;
    }
    DD ret=0;
    int sm=m,sM=M;
    while(m!=sM || M!=sm){
        ret=max(ret,norm(g[m]-g[M]));
        if(cross(g[(m+1)%gz]-g[m],g[(M+1)%gz]-g[M])<0) m=(m+1)%gz;
        else M=(M+1)%gz;
    }
    return sqrt(ret);
}

//凸多角形gをlで切断
//l.p1-l.p2の左側
//gは反時計回り→反時計回りで返す
//時計回り→時計回り
Polygon ConvexCut(const Polygon &g,const Line &l){
    Polygon ret;
    int gz=(int)g.size();
    for(int i=0;i<gz;i++){
        P now=g[i],next=g[(i+1)%gz];
        if(ccw(l.a,l.b,now)>=0) ret.push_back(now);
        if(ccw(l.a,l.b,now)*ccw(l.a,l.b,next)<0){
            ret.push_back(crossPoint(Line(now,next),l));
        }
    }
    return ret;
}

inline DD calc(const P &a,const P &b,const DD &r,const bool triangle){
    if(triangle) return cross(a,b);
    else return r*r*arg(b/a);
}

DD calcArea(const DD &r,const P &a,const P &b){
    if(eq(abs(a-b),0)) return 0;
    bool ina=abs(a)<r+EPS;
    bool inb=abs(b)<r+EPS;
    if(ina && inb) return cross(a,b);
    auto cr=crossPointSC(Segment(a,b),Circle((0,0),r));
    if(cr.empty()) return calc(a,b,r,false);
    auto s=cr[0],t=cr.back();
    return calc(s,t,r,true)+calc(a,s,r,ina)+calc(t,b,r,inb);
}

//円と多角形の共通部分の面積
//http://drken1215.hatenablog.com/entry/2020/02/02/091000
DD Area(const Circle &c,const Polygon &g){
    DD ret=0.0;
    int gz=g.size();
    if(gz<3) return ret;
    for(int i=0;i<gz;i++){
        P a=g[i]-c.p,b=g[(i+1)%gz]-c.p;
        ret+=calcArea(c.r,g[i]-c.p,g[(i+1)%gz]-c.p);
    }
    return ret/2.0;
}

//++++なんか凄いの+++++++++++++++

//最近点対
DD RecClosetPair(Polygon::iterator it,const int n){
    if(n<=1) return INF;
    int m=n/2;
    DD x=real(it[m]);
    DD d=min(RecClosetPair(it,m),RecClosetPair(it+m,n-m));
    inplace_merge(it,it+m,it+n,yx);
    Polygon v;
    for(int i=0;i<n;i++){
        if(abs(real(it[i])-x)>=d) continue;
        for(int j=0;j<v.size();j++){
            DD dy=imag(it[i])-imag(v[v.size()-1-j]);
            if(dy>=d) break;
            DD dx=real(it[i])-real(v[v.size()-1-j]);
            d=min(d,sqrt(dx*dx+dy*dy));
        }
        v.push_back(it[i]);
    }
    return d;
}

DD ClosetPair(Polygon g){
    sort(g.begin(),g.end(),xy);
    return RecClosetPair(g.begin(),g.size());
}




signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    cout<<fixed<<setprecision(10);
    
    int N;
    DD r;
    cin>>N>>r;
    Polygon g;
    while(N--){
        DD x,y;
        cin>>x>>y;
        g.emplace_back(x,y);
    }
    cout<<Area(Circle((0,0),r),g)<<endl;
}