#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
#include<stack>
#include<set>
#include<string>
#include<map>
#include<cmath>
#include<bitset>
using namespace std;
#define pb push_back
#define pf push_front
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mst(x,a) memset(x,a,sizeof(x))
#define all(x) (x).begin(),(x).end()
#define CLOSE ios::sync_with_stdio(false)
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
#define fi first
#define se second
#define sz(x) ((int)x.size())
#define cl(x) x.clear()
const int N = 100100;
const int M = 200010;
const ll inf = 1e15;
const int mod=1000000007;
ll qpow(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b/=2;}return ans;}
ll qpow(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c;b/=2;}return ans;}
const double eps = 1e-8,pi=acos(-1);


/*
名字规范:判断类：Is (行为) A To B /Is (行为) A
        询问类: Get (行为) A To B / Get(行为) A

平行:Parallel
正交:Orthogonal
切线:Tangent
*/

//-----------------------------------------------------------------------------------------------------------------
// 基础篇

int dcmp(double x) {
    if(fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    void read(){ scanf("%lf%lf",&x,&y);}
    void print(){ printf("%f %f\n",x,y);}
    bool operator < (const Point &rhs)const{
        return dcmp(x - rhs.x)<0 || ( dcmp(x - rhs.x)==0 && dcmp(y -rhs.y)<0);
    }
    bool operator == (const Point &rhs)const{
        return dcmp(x - rhs.x) == 0 && dcmp(y - rhs.y) == 0;
    }
};

typedef Point Vector;

struct Circle {
    Point c;
    double r;
    Circle(Point c = Point(0, 0), double r = 0):c(c),r(r){}
    Point getPoint(double rad) {
        return Point(cos(rad) * r + c.x, sin(rad) * r + c.y);
    }
};

Point operator + (Vector A, Vector B) {return Point(A.x + B.x, A.y + B.y);}
Point operator - (Vector A, Vector B) {return Point(A.x - B.x, A.y - B.y);}
Point operator * (Vector A, double p) {return Point(A.x * p, A.y * p);}
Point operator / (Vector A, double p) {return Point(A.x / p, A.y / p);}

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 Angle(Vector A, Vector B) {//精度很差，应当观察题目推导公式来提高精度
    double b=A.x*A.x+A.y*A.y,c=B.x*B.x+B.y*B.y,a=(A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
    double d=2.0*sqrt(b)*sqrt(c);
    return acos((b+c-a)/d);
}//似乎是角度的绝对值。。。

double Angle(Vector a){
    return atan2(a.y,a.x);
}

double Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}//>0 B在A的逆时针方向

// 向量逆时针旋转 rad 弧度
Vector Rotate(Vector A, double rad) {return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));}
// 两点距离比Length精度要高
double dist(Point a, Point b) {return sqrt((a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y));}
//弧度转化角度
double RadToDegree(double rad){	return rad/pi*180;}
//角度转化弧度
double DegreeToRad(double deg){ return deg/180*pi;}


struct Line{
    Point a,b;
    Line(Point x=Point(0,0),Point y=Point(0,0)):a(x),b(y){}
    Line(Point p,double ang){	//一个点和斜率(弧度制)确定直线
		a=p;
		if(dcmp(ang-pi/2)==0) b=a+Point(0,1);
		else b=a+Point(1,tan(ang));
	}
	Line(double x,double y,double z){	//ax+by+c=0
		if(dcmp(x)==0){
			a=Point(0,-z/y);
			b=Point(1,-z/y);
		}
		else if(dcmp(y)==0){
			a=Point(-z/x,0);
			b=Point(-z/x,1);
		}
		else{
			a=Point(0,-z/y);
			b=Point(1,(-z-x)/y);
		}
	}
    //极角排序，在半平面交中不能用叉积判，因为叉积沒方向(也许配合点积可以实现)
    bool operator <(const Line& rhs) const{
        double x=atan2(b.y-a.y,b.x-a.x),y=atan2(rhs.b.y-rhs.a.y,rhs.b.x-rhs.a.x);//返回与x轴正向夹角(-pi~pi]
        if(dcmp(x-y)==0) return dcmp(Cross(rhs.b-rhs.a,a-rhs.a))>0;
        return dcmp(x-y)<0;
    }
    void read(){scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);}
    void print(){ printf("%f %f %f %f\n",a.x,a.y,b.x,b.y);}
};
//正数表示向直线表示的左边移动
Line translation(Line p,double y){
    Point x=p.b-p.a;
    x=Rotate(x,pi/2);
    x=x/Length(x); x=x*y;
    p.a=p.a+x; p.b=p.b+x;
    return p;
}
//-----------------------------------------------------------------------------------------------------------------
//点线篇

// 点是否在线段上 OK
bool IsOnPointToSegment(const Point &p, const Point &a1, const Point &a2) {
    if(dcmp(Cross(a1-p,a2-p))) return false;
    else if(dcmp(p.x-min(a1.x,a2.x)) >= 0 && dcmp(p.x-max(a1.x,a2.x)) <= 0
            && dcmp(p.y-min(a1.y,a2.y)) >= 0 && dcmp(p.y-max(a1.y,a2.y)) <= 0) return true;
    else return false;
}

//点到直线
double GetDistancePointToLine(Point p,Line x){
    Point a=x.a,b=x.b;
    Vector v1=b-a,v2=p-a;
    return fabs(Cross(v1,v2))/Length(v1);
}

//点到线段的距离 OK
double GetDistancePointToSegment(Point p,Line x){
    if(x.a==x.b) return Length(p-x.a);
    Vector v1=x.b-x.a,v2=p-x.a,v3=p-x.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);
}

//点在直线上的投影 OK
Point GetProjectionPointToLine(Point p,Line x){
    Vector v=x.b-x.a;
    return x.a+v*(Dot(v,p-x.a)/Dot(v,v));
}

//点关于直线的对称点 OK
Point GetReflectionPointToLine(Point p,Line x){
    Point y=GetProjectionPointToLine(p,x);
    return p+(y-p)*2.0;
}

//两线是否平行 OK
bool IsParallelLineToLine(Line x,Line y){
    Point a=x.a-x.b,b=y.a-y.b;
    if(dcmp(Cross(a,b))==0) return true;
    return false;
}

//两线段是否正交 OK
bool IsOrthogonalLineToLine(Line x,Line y){
    Point a=x.a-x.b,b=y.a-y.b;
    double w=Dot(a,b);
    if(dcmp(w)==0) return true;
    return false;
}

//线段相交(包含端点相交) OK
bool IsIntersectionSegmentToSegment1(Line x,Line y){
    Point a=x.a,b=x.b,c=y.a,d=y.b;
    double a1=Cross(b-a,d-a),a2=Cross(c-a,b-a),a3=Cross(d-c,a-c),a4=Cross(b-c,d-c);
    return dcmp(a1)*dcmp(a2)>=0&&dcmp(a3)*dcmp(a4)>=0
         &&max(c.x,d.x)>=min(a.x,b.x)&&max(a.x,b.x)>=min(c.x,d.x)
         &&max(c.y,d.y)>=min(a.y,b.y)&&max(a.y,b.y)>=min(c.y,d.y);
}

//线段相交(不包含端点相交) 两直线重合算不相交 OK
bool IsIntersectionSegmentToSegment2(Line x,Line y){
    Point a=x.a,b=x.b,c=y.a,d=y.b;
    double a1=Cross(b-a,d-a),a2=Cross(c-a,b-a),a3=Cross(d-c,a-c),a4=Cross(b-c,d-c);
    return dcmp(a1)*dcmp(a2)>0&&dcmp(a3)*dcmp(a4)>0;
}

//线段与直线相交 OK
bool IsIntersectionSegmentToLine(Line x,Line y){//x是线段 y是直线
    if(dcmp(Cross(x.a-y.b,y.a-y.b))*dcmp(Cross(y.a-y.b,x.b-y.b))>=0) return true;
    return false;
}

//两直线相交 调用前保证两直线不平行 OK
Point GetIntersectionLineToLine(Line x,Line y){
    Point a=x.a,b=x.b-x.a;
    Point c=y.a,d=y.b-y.a;
    Point u=a-c;
    double t=Cross(d,u)/Cross(b,d);//Cross(b,d)!=0，这个的意思就是平行
    return a+b*t;
}

//两线段距离 OK
double GetDistanceSegmentToSegment(Line x,Line y){
    if(IsIntersectionSegmentToSegment1(x,y)) return 0;
    double v1=min(GetDistancePointToLine(x.a,y),GetDistancePointToLine(x.b,y));
    double v2=min(GetDistancePointToLine(y.a,x),GetDistancePointToLine(y.b,x));
    return min(v1,v2);
}

//-----------------------------------------------------------------------------------------------------------------

//多边形面积，需按顺时针或逆时针给出 OK
double GetAreaPolygon(vector<Point>& p) {
    int n = p.size();
    double area = 0;
    for(int i = 1; i < n - 1; i++)
        area += Cross(p[i]-p[0], p[i+1]-p[0]);
    return fabs(area / 2);
}

//多边形周长，需按顺时针或逆时针给出 OK
double GetPerimeterPolygon(vector<Point>& p){
    if(p.size()==0||p.size()==1) return 0;
    double ret=dist(p[0],p[p.size()-1]);
    for(int i=0;i<p.size()-1;i++)
        ret+=dist(p[i+1],p[i]);
    return ret;
}

// 判断点是否在多边形内 OK
int IsInPointToPolygon(Point p,vector<Point>& poly) {
    int wn = 0,n=poly.size();
    for(int i = 0; i < n; i++) {
        if(IsOnPointToSegment(p, poly[i], poly[(i+1)%n])) return -1; //在边界上
        int k = dcmp(Cross(poly[(i+1)%n]-poly[i], p-poly[i]));
        int d1 = dcmp(poly[i].y-p.y);
        int d2 = dcmp(poly[(i+1)%n].y-p.y);
        if(k>0 && d1<=0 && d2>0) wn++;
        if(k<0 && d2<=0 && d1>0) wn--;
    }
    if(wn != 0) return 1; //内部
    return 0; //外部
}

//判断线段与多边形关系
int IsInSegmentToPolygon(vector<Point>& poly,Line x){//0 外部 1 内部 -1相交
    for(int i=1;i<sz(poly);i++){
        if(IsIntersectionSegmentToSegment1(Line(poly[i],poly[i-1]),x)){
            return -1;
        }
    }
    if(sz(poly)>1)
        if(IsIntersectionSegmentToSegment1(Line(poly[0],poly[poly.size()-1]),x))
            return -1;
    if(IsInPointToPolygon(x.a,poly)==1) return 1;
    return 0;
}

//判断是否为凸包 OK
bool IsConvexPolygon(vector<Point>& p){
    int n = p.size();
    if(dcmp(Cross(p[0]-p[n-1], p[1]-p[0]))*dcmp(Cross(p[n-1]-p[n-2],p[0]-p[n-1]))<0)
        return false;
    for(int i = 2; i < n - 1; i++)
        if(dcmp(Cross(p[i]-p[i-1], p[i+1]-p[i]))*dcmp(Cross(p[i-1]-p[i-2], p[i]-p[i-1]))<0)
            return false;
    return true;
}

//由矩形对角的两个点求出另外两个点(a,b 为已知)
void GetRectanglePoint(Point a,Point b,Point &c,Point &d){
    c.x=(a.x+b.x+b.y-a.y)/2;
    c.y=(a.y+b.y+a.x-b.x)/2;
    d.x=(a.x+b.x-b.y+a.y)/2;
    d.y=(a.y+b.y-a.x+b.x)/2;
}
//多边形是否相交
bool IsIntersectionPolygonToPolygon(vector<Point> &a,vector<Point> &b){
    int n=a.size(),m=b.size();
    for(int i=0;i<n;i++){
        Line x; x.a=a[i]; x.b=a[(i+1)%n];
        for(int j=0;j<m;j++){
            Line y; y.a=b[j]; y.b=b[(j+1)%m];
            if(IsIntersectionSegmentToSegment1(x,y)) return true;
        }
    }
    return false;
}

//算凸包 凸包是一条直线要特判 OK
void GetConvexPolygon(vector<Point> &p, vector<Point>& ch) {
    int n = p.size(), m = 0;
    sort(p.begin(), p.end());
    for(int i = 0; i < n; i++) {
        while(m > 1 && dcmp(Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) < 0) ch.pop_back(), m--;//点最少写上=
        ch.push_back(p[i]); m++;
    }
    int k = m;
    for(int i = n - 2; i >= 0; i--) {
        while(m > k && dcmp(Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) < 0) ch.pop_back(), m--;//这里也写
        ch.push_back(p[i]); m++;
    }
    if(n>1) ch.pop_back(),m--;
}

//得到凸包直径(最大) OK 注意一条直线的情况
double GetDiameterConvex(vector<Point>& p){
    if(sz(p)==1) return 0;
    if(sz(p)==2) return Length(p[1]-p[0]);
    double ret=0;
    for(int i=0,x=0;i<sz(p);i++){
        while(Cross(p[i]-p[i+1],p[i+1]-p[(x+1)%sz(p)])>=Cross(p[i]-p[i+1],p[i+1]-p[x])) x=(x+1)%sz(p);//逆时针>=
        ret=max(ret,max(Length(p[x]-p[i]),Length(p[x]-p[i+1])));
    }
    return ret;
}

////多边形面积并
//double Seg(Point O, Point A, Point B){
//    if(dcmp(B.x - A.x) == 0) return (O.y - A.y) / (B.y - A.y);
//    return (O.x - A.x) / (B.x - A.x);
//}
//
//double MultiPolyArea(vector<Point>* p, int n) {
//    double res=0;
//    vector<pair<double, int>> s;
//    for(int i = 0; i < n; i++) {
//        int sz = p[i].size();
//        for(int j = 0; j < sz; j++){
//            s.clear();
//            s.push_back({0, 0});
//            s.push_back({1, 0});
//            Point a = p[i][j], b = p[i][(j+1)%sz];
//            for(int k = 0; k < n; k++){
//                if(i != k){
//                    int sz2 = p[k].size();
//                    for(int z = 0; z < sz2; z++){
//                        Point c = p[k][z], d = p[k][(z+1)%sz2];
//                        int c1 = dcmp(Cross(b-a, c-a));
//                        int c2 = dcmp(Cross(b-a, d-a));
//                        if(c1 == 0 && c2 == 0) {
//                            if(dcmp(Cross(b-a, d-c))) {
//                                s.push_back({Seg(c, a, b), 1});
//                                s.push_back({Seg(c, a, b), -1});
//                            }
//                        } else {
//                            double s1 = Cross(d-c, a-c), s2 = Cross(d-c, b-c);
//                            if(c1 >= 0 && c2 < 0) s.push_back({s1/(s1-s2), 1});
//                            else if(c1 < 0 && c2 >= 0) s.push_back({s1/(s1-s2), -1});
//                        }
//                    }
//                }
//            }
//            sort(s.begin(), s.end());
//            double pre = min(max(s[0].fi, 0.0), 1.0), now, sum=0;
//            int cov = s[0].se;
//            for(int j = 1; j < s.size(); j++) {
//                now = min(max(s[j].fi, 0.0), 1.0);
//                if(!cov) sum += now - pre;
//                cov += s[j].second;
//                pre = now;
//            }
//            res += Cross(a, b) * sum;
//        }
//    }
//    return fabs(res / 2);
//}

//-----------------------------------------------------------------------------------------------------------------
//半平面

//q[]是向量队列
//t[i]是s[i-1]与s[i]的交点
//队列的范围是(l,r]
//如果返回的凸包点数<=2则无解
//但是还是有可能出现点数大于2但是依旧无解，需要判断下面积是否为0来规避这种情况
void GetConVexHalfplane(vector<Line> &v,vector<Point> &ret){
    Point t[N]; Line q[N];//记得拿出去
    sort(all(v));
    int l=0,r=0,n=v.size();

    for(int i=0;i<n;++i){ //先队尾再队首
        if(i&&dcmp(atan2(v[i].b.y-v[i].a.y,v[i].b.x-v[i].a.x)-atan2(v[i-1].b.y-v[i-1].a.y,v[i-1].b.x-v[i-1].a.x))==0)
            continue;
        //如果上一个交点在向量右侧则弹出队尾
        while(r-l>1&&dcmp(Cross(v[i].a-v[i].b,t[r]-v[i].b))>0) --r;
        //如果第一个交点在向量右侧则弹出队首
        while(r-l>1&&dcmp(Cross(v[i].a-v[i].b,t[l+2]-v[i].b))>0) ++l;
        q[++r]=v[i];
        if(r-l>1) t[r]=GetIntersectionLineToLine(q[r],q[r-1]);//求新交点
    }
    while(r-l>1&&dcmp(Cross(q[l+1].a-q[l+1].b,t[r]-q[l+1].b))>0)//注意删除多余元素
        --r;
    t[r+1]=GetIntersectionLineToLine(q[l+1],q[r]);//再求出新的交点
    ++r;
    for(int i=l+2;i<=r;i++) ret.pb(t[i]);
}

//-----------------------------------------------------------------------------------------------------------------
//圆
//圆的面积
double GetAreaCircle(Circle a){
    return pi*a.r*a.r;
}

// 三点确定圆心
Point GetCircleCenter(Point A, Point B, Point C) {
    Point o;
    double a1 = B.x-A.x, b1 = B.y-A.y, c1 = (a1*a1+b1*b1)/2;
    double a2 = C.x-A.x, b2 = C.y-A.y, c2 = (a2*a2+b2*b2)/2;
    double d = a1*b2-a2*b1;
    o.x=A.x+(c1*b2-c2*b1)/d;
    o.y=A.y+(a1*c2-a2*c1)/d;
    return o;
}

//判断圆与圆的关系
//0 相离 1外切
//2 内切 3内含 4 相交
int IsIntersectionCircleToCircle(Circle a,Circle b){
    double d=dist(a.c,b.c);
    if(dcmp(d-a.r-b.r)>0) return 0;
    if(dcmp(d-a.r-b.r)==0) return 1;
    if(dcmp(d+min(a.r,b.r)-max(a.r,b.r))==0) return 2;
    if(dcmp(d+min(a.r,b.r)-max(a.r,b.r))>0) return 4;
    return 3;
}

//判断线段与圆的关系 1 相交 -1内部 -2 外部
int IsIntersectionSegmentToCircle(Line a,Circle b){
    double len1=GetDistancePointToSegment(b.c,a);
    double len2=max(dist(a.a,b.c),dist(a.b,b.c));
    if(dcmp(len1-b.r)<=0&&dcmp(len2-b.r)>=0) return 1;
    if(dcmp(len1-b.r)<0&&dcmp(len2-b.r)<0) return -1;
    if(dcmp(len1-b.r)>0&&dcmp(len2-b.r)>0) return -2;
}

//两圆的相交面积
double GetAreaCircleToCircle(Circle a,Circle b){
    int x=IsIntersectionCircleToCircle(a,b);
    if(x==0||x==1) return 0;
    if(x==3||x==2) return min(GetAreaCircle(a),GetAreaCircle(b));
    double d=dist(a.c,b.c);
    if(dcmp(a.r-b.r)>0) swap(a,b);
	double ang1=acos((a.r*a.r+d*d-b.r*b.r)/(2.0*a.r*d));
	double ang2=acos((b.r*b.r+d*d-a.r*a.r)/(2.0*b.r*d));
	return ang1*a.r*a.r + ang2*b.r*b.r - a.r*d*sin(ang1);
}

//圆与直线的交点
int GetIntersectionLineToCircle(Circle a,Line b,Point &p1,Point &p2){
    double d=GetDistancePointToLine(a.c,b);
    if(dcmp(d-a.r)>0) return 0;
    Point p=GetProjectionPointToLine(a.c,b);
    double x=sqrt(a.r*a.r-d*d);
    Point v;
    if(p==a.c) v=b.a-b.b;
    else v=Rotate(p-a.c,pi/2);
    v=v/Length(v);
    p1=p+v*x; p2=p-v*x;
    if(dcmp(d-a.r)==0) return 1;
    return 2;
}

//两圆的交点
int GetIntersectionCircleToCircle(Circle a,Circle b,Point &p1,Point &p2){
    if(a.r>b.r) swap(a,b);
    double r=a.r,R=b.r,d=Length(a.c-b.c);
    if(dcmp(d)==0&&a.c==b.c) return 0;//重合
    if(R>d+r||d>R+r) return 0;
    double cos_ang=(r*r+d*d-R*R)/(2.0*r*d);
    double sin_ang=sqrt(1.0-cos_ang*cos_ang);
    Point o=(b.c-a.c)*(1.0/d);
    o=a.c+o*(r*cos_ang);
    Point pt=Point(a.c.y-b.c.y,b.c.x-a.c.x)*(1.0/d);
    p1=o+pt*(r*sin_ang);
    p2=o-pt*(r*sin_ang);
    if(dcmp(p1.x-p2.x)==0&&dcmp(p1.y-p2.y)==0) return 1;
    return 2;
}

//圆与直线的切点
int GetTangentPointToCircle(Circle a,Point b,Point &p1,Point &p2){
    double d=Length(a.c-b);
    if(dcmp(d-a.r)<0) return -1;
    if(dcmp(d-a.r)==0){
        //Point x=Rotate(b-a,pi/2);
        //x=x+b;
        return 1;
    }
    Point x=Rotate(b-a.c,acos(a.r/d));
    p1=x/Length(x)*a.r+a.c;
    x=Rotate(b-a.c,-acos(a.r/d));
    p2=x/Length(x)*a.r+a.c;
    return 2;
}

//圆是否在多边形内
bool IsInCircleToPolygon(vector<Point> &v,Circle a){
    for(int i=0;i<sz(v);i++){
        Line t; t.a=v[i]; t.b=v[(i+1)%sz(v)];
        if(IsIntersectionSegmentToCircle(t,a)!=-2) return false;
    }
    if(IsInPointToPolygon(a.c,v)) return true;
    return false;
}

//求凸包最大内切圆
double GetCircleConvex(vector<int> v){
    int n=v.size();
    double l=0,r=10000;
    for(int i=0;i<30;i++){
        double m=(l+r)/2.0;
        vector<Line> tp;
        for(int j=0;j<n;j++) tp.pb(Line(v[j],v[(j+1)%n]));
        for(int j=0;j<n;j++) tp[j]=translation(tp[j],m);
        vector<Point> c;
        GetConVexHalfplane(tp,c);
        if(sz(c)<3) r=m;
        else l=m;
    }
    return r;//下面是求圆心的过程
    vector<Line> tp;
    for(int i=0;i<n;i++) tp.pb(Line(v[i],v[(i+1)%n]));
    for(int i=0;i<n;i++) tp[i]=translation(tp[i],r);
    vector<Point> c;
    GetConVexHalfplane(tp,c);
    //c这个凸包中任意一个点都能作为圆心
}

//圆是否内含,b在a内(边界有接触也算)
bool IsInCircleToCirlce(Circle a,Circle b){
    double d=Length(b.c-a.c);
    if(dcmp(d-a.r)>0) return false;
    if(dcmp(d+b.r-a.r)<=0) return true;
    return false;
}

//多个圆并
double GetAreaCircles(vector<Circle> &v){
    bool del[N]; //写的时候扔出去
    double ans = 0;
    for(int i = 0; i < sz(v); ++i) {
        for(int j = 0; j < sz(v); ++j) if(!del[j]) {
            if(i == j) continue;
            if(IsInCircleToCirlce(v[j],v[i])){
                del[i] = true;
                break;
            }
        }
    }//删内含
    for(int i = 0; i < sz(v); ++i) if(!del[i]) {
        Circle &mc = v[i];
        Point p1, p2;
        bool flag = false;
        vector<pair<double,double> > reg;
        for(int j = 0; j < sz(v); ++j) if(!del[j]) {
            if(i == j) continue;
            if(GetIntersectionCircleToCircle(mc,v[j],p1,p2)!=2) continue;
            if(mc.r>v[j].r) swap(p1,p2);
            flag = true;
            double rs = Angle(p2-mc.c),rt = Angle(p1 - mc.c);
            if(dcmp(rs) < 0) rs += 2 * pi;
            if(dcmp(rt) < 0) rt += 2 * pi;
            if(dcmp(rs - rt) > 0){
                reg.pb({rs, pi * 2}),reg.pb({0, rt});
            }
            else reg.pb({rs, rt});
        }//
        if(!flag) { //与其他圆没有相交
            ans += pi * mc.r * mc.r;
            continue;
        }
        sort(all(reg));
        int cnt = 1;
        for(int j = 1; j < sz(reg); ++j) {
            if(dcmp(reg[cnt - 1].se-reg[j].fi) >= 0) {
                reg[cnt - 1].se =
                max(reg[cnt - 1].se, reg[j].se);
            } else reg[cnt++] = reg[j];
        }//算剩余圆上面积
        reg.pb(reg[0]);
        reg[cnt]=reg[0];
        for(int j = 0; j < cnt; ++j) {
            p1 = Rotate(Point(1,0),reg[j].se);
            p1=p1/Length(p1)*mc.r+mc.c;
            p2 = Rotate(Point(1,0),reg[j+1].fi);
            p2=p2/Length(p2)*mc.r+mc.c;
            ans += Cross(p1, p2) / 2;
            double angle = reg[j + 1].fi -
            reg[j].se;
            if(dcmp(angle) < 0) angle += 2 * pi;
            ans += 0.5 * mc.r * mc.r *
            (angle - sin(angle));
        }
    }
    return ans;
}

//圆与三角形交(其中一个三角形定点在圆心) 面积有正负之分
double GetAreaTriangleToCircle1(Circle C,Point A,Point B){
    Vector OA = A-C.c, OB = B-C.c;
    Vector BA = A-B, BC = C.c-B;
    Vector AB = B-A, AC = C.c-A;
    double DOA = Length(OA), DOB = Length(OB),DAB = Length(AB), r = C.r;
    if(dcmp(Cross(OA,OB)) == 0) return 0;
    if(dcmp(DOA-C.r) < 0 && dcmp(DOB-C.r) < 0) return Cross(OA,OB)*0.5;
    else if(DOB < r && DOA >= r) {
        double x = (Dot(BA,BC) + sqrt(r*r*DAB*DAB-Cross(BA,BC)*Cross(BA,BC)))/DAB;
        double TS = Cross(OA,OB)*0.5;
        return asin(TS*(1-x/DAB)*2/r/DOA)*r*r*0.5+TS*x/DAB;
    }
    else if(DOB >= r && DOA < r) {
        double y = (Dot(AB,AC)+sqrt(r*r*DAB*DAB-Cross(AB,AC)*Cross(AB,AC)))/DAB;
        double TS = Cross(OA,OB)*0.5;
        return asin(TS*(1-y/DAB)*2/r/DOB)*r*r*0.5+TS*y/DAB;
    }
    else if(fabs(Cross(OA,OB)) >= r*DAB || Dot(AB,AC) <= 0 || Dot(BA,BC) <= 0) {
        if(Dot(OA,OB) < 0){
            if(Cross(OA,OB) < 0) return (-acos(-1.0)-asin(Cross(OA,OB)/DOA/DOB))*r*r*0.5;
            else return ( acos(-1.0)-asin(Cross(OA,OB)/DOA/DOB))*r*r*0.5;
        }
        else return asin(Cross(OA,OB)/DOA/DOB)*r*r*0.5;
    }
    else {
        double x = (Dot(BA,BC)+sqrt(r*r*DAB*DAB-Cross(BA,BC)*Cross(BA,BC)))/DAB;
        double y = (Dot(AB,AC)+sqrt(r*r*DAB*DAB-Cross(AB,AC)*Cross(AB,AC)))/DAB;
        double TS = Cross(OA,OB)*0.5;
        return (asin(TS*(1-x/DAB)*2/r/DOA)+asin(TS*(1-y/DAB)*2/r/DOB))*r*r*0.5 + TS*((x+y)/DAB-1);
    }
}

double rad(Point a,Point b){	//两个向量的夹角
	return fabs(atan2(fabs(Cross(a,b)),Dot(a,b)));
}


double circle_traingle_area(Point a,Point b,Circle c){	//a,b与圆心c所围成的三角形与圆围成的面积
	Point p=c.c;
	double r=c.r;
	if(dcmp(Cross(p-a,p-b))==0)	return 0;
	Point q[5];
	int len=0;
	q[len++]=a;
	Line l(a,b);
	Point p1,p2;
	if(GetIntersectionLineToCircle(c,l,q[1],q[2])==2){
		if(dcmp(Dot(a-q[1],b-q[1]))<0)	q[len++]=q[1];
		if(dcmp(Dot(a-q[2],b-q[2]))<0)	q[len++]=q[2];
	}
	q[len++]=b;
	if(len==4&&dcmp(Dot(q[0]-q[1],q[2]-q[1]))>0)	swap(q[1],q[2]);
	double res=0;
	for(int i=0;i<len-1;i++){//直线和圆的位置关系  0:相离   1:相切   2:相交
		if(dcmp(dist(q[i],c.c)-c.r)>0||dcmp(dist(q[i+1],c.c)-c.r)>0){
			double arg=rad(q[i]-p,q[i+1]-p);
			res+=r*r*arg/2;
		}
		else res+=fabs(Cross(q[i]-p,q[i+1]-p)/2);
	}
	return res;
}

//圆与三角形交(三个点均不再圆心，实际上就是将一个三角形拆成三个) 面积有正负之分
double GetAreaTriangleToCircle2(Circle x,Point a,Point b,Point c){

}

//圆与多边形交(利用三角剖分)
double GetAreaCircleToPolygon(Circle x,vector<Point> &v){
    double ret=0;
    for(int i=0;i<sz(v);i++){
        ret+=1.0*dcmp(Cross(v[i]-x.c,v[(i+1)%sz(v)]-x.c))*circle_traingle_area(v[i],v[(i+1)%sz(v)],x);
    }
    return fabs(ret);
}

//两圆共切线
int GetTangentCircleToCircle(Circle A, Circle B, vector<Point>& a, vector<Point>& b) {
    if(A.r < B.r) swap(A, B), swap(a, b);
    double d2 = (A.c.x-B.c.x)*(A.c.x-B.c.x)+(A.c.y-B.c.y)*(A.c.y-B.c.y);
    double rdiff = A.r - B.r;
    double rsum = A.r + B.r;
    if(dcmp(d2 - rdiff * rdiff) < 0) return 0;
    double base = atan2(B.c.y-A.c.y,B.c.x-A.c.x);
    if(d2 == 0 && dcmp(A.r - B.r) == 0) return -1;
    if(dcmp(d2 - rdiff * rdiff) == 0) {
        a.push_back(A.getPoint(base));
        b.push_back(B.getPoint(base));
        return 1;
    }
    //有公切线
    double ang = acos((A.r - B.r) / sqrt(d2));
    a.push_back(A.getPoint(base+ang)); b.push_back(B.getPoint(base+ang));
    a.push_back(A.getPoint(base-ang)); b.push_back(B.getPoint(base-ang));
    if(dcmp(d2 - rsum * rsum) == 0) {
        a.push_back(A.getPoint(base)); b.push_back(B.getPoint(pi+base));
    } else if(dcmp(d2 - rsum * rsum) > 0) {
        double ang = acos((A.r + B.r) / sqrt(d2));
        a.push_back(A.getPoint(base+ang)); b.push_back(B.getPoint(pi+base+ang));
        a.push_back(A.getPoint(base-ang)); b.push_back(B.getPoint(pi+base-ang));
    }
    return (int)a.size();
}

// 给出若干个点求最小圆覆盖这些点
void MinPointCoverByCircle(Point *p, int n, Point &o, double &r) {
    random_shuffle(p, p+n);
    o = p[0], r = 0;
    for(int i = 1; i < n; i++) {
        if(dist(p[i], o) > r + eps) {
            o = p[i]; r = 0;
            for(int j = 0; j < i; j++) {
                if(dist(p[j], o) > r + eps) {
                    o.x = (p[i].x+p[j].x)/2;
                    o.y = (p[i].y+p[j].y)/2;
                    r = dist(p[j], o);
                    for(int k = 0; k < j; k++) {
                        if(dist(p[k], o) > r + eps) {
                            o = GetCircleCenter(p[i], p[j], p[k]);
                            r = dist(p[i], o);
                        }
                    }
                }
            }
        }
    }
}

//--------------------------------------------------------------------------------------------------------

int main(){
    Circle x; x.c.x=0; x.c.y=0; int n;
    scanf("%d%lf",&n,&x.r);
    vector<Point> v;
    for(int i=0;i<n;i++){
        Point p; p.read();
        v.pb(p);
    }
    double ret=GetAreaCircleToPolygon(x,v);
    printf("%.12f\n",ret+eps);
}
/*
3
1 1 1
2 1 1
3 1 1
*/



Measured memory_bytes: 3720