#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a> (istream &is,Point &p){ is>>p.x>>p.y; return is; } ostream &operator << (ostream &os,Point p){ os< Polygon; istream &operator >> (istream &is,Polygon &p){ for(int i=0;i<(int)p.size();i++) is>>p[i]; return is; } struct Segment{ Point p1,p2; Segment(){} Segment(Point p1, Point p2):p1(p1),p2(p2){} }; typedef Segment Line; istream &operator >> (istream &is,Segment &s){ is>>s.p1>>s.p2; return is; } struct Circle{ Point c; double r; Circle(){} Circle(Point c,double r):c(c),r(r){} }; istream &operator >> (istream &is,Circle &c){ is>>c.c>>c.r; return is; } double norm(Vector a){ return a.x*a.x+a.y*a.y; } double abs(Vector a){ return sqrt(norm(a)); } double dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y; } double cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x; } Point orth(Point p){return Point(-p.y,p.x);} bool isOrthogonal(Vector a,Vector b){ return equals(dot(a,b),0.0); } bool isOrthogonal(Point a1,Point a2,Point b1,Point b2){ return isOrthogonal(a1-a2,b1-b2); } bool isOrthogonal(Segment s1,Segment s2){ return equals(dot(s1.p2-s1.p1,s2.p2-s2.p1),0.0); } bool isParallel(Vector a,Vector b){ return equals(cross(a,b),0.0); } bool isParallel(Point a1,Point a2,Point b1,Point b2){ return isParallel(a1-a2,b1-b2); } bool isParallel(Segment s1,Segment s2){ return equals(cross(s1.p2-s1.p1,s2.p2-s2.p1),0.0); } Point project(Segment s,Point p){ Vector base=s.p2-s.p1; double r=dot(p-s.p1,base)/norm(base); return s.p1+base*r; } Point reflect(Segment s,Point p){ return p+(project(s,p)-p)*2.0; } double arg(Vector p){ return atan2(p.y,p.x); } Vector polar(double a,double r){ return Point(cos(r)*a,sin(r)*a); } int ccw(Point p0,Point p1,Point p2); bool intersectSS(Point p1,Point p2,Point p3,Point p4); bool intersectSS(Segment s1,Segment s2); bool intersectPS(Polygon p,Segment l); int intersectCC(Circle c1,Circle c2); bool intersectSC(Segment s,Circle c); double getDistanceLP(Line l,Point p); double getDistanceSP(Segment s,Point p); double getDistanceSS(Segment s1,Segment s2); Point getCrossPointSS(Segment s1,Segment s2); Point getCrossPointLL(Line l1,Line l2); Polygon getCrossPointCL(Circle c,Line l); Polygon getCrossPointCC(Circle c1,Circle c2); int contains(Polygon g,Point p); Polygon andrewScan(Polygon s); Polygon convex_hull(Polygon ps); double diameter(Polygon s); bool isConvex(Polygon p); double area(Polygon s); Polygon convexCut(Polygon p,Line l); Line bisector(Point p1,Point p2); Vector translate(Vector v,double theta); vector corner(Line l1,Line l2); vector > > segmentArrangement(vector &ss, Polygon &ps); int ccw(Point p0,Point p1,Point p2){ Vector a = p1-p0; Vector b = p2-p0; if(cross(a,b) > EPS) return CCW_COUNTER_CLOCKWISE; if(cross(a,b) < -EPS) return CCW_CLOCKWISE; if(dot(a,b) < -EPS) return CCW_ONLINE_BACK; if(a.norm()r) return ICC_SEPERATE; if(equals(d+c2.r,c1.r)) return ICC_INSCRIBE; if(d+c2.rEPS) return 0; double d1=abs(c.c-s.p1),d2=abs(c.c-s.p2); if(d1c.r+EPS)||(d1>c.r+EPS&&d21u){ if(dot(l.p1-res[0],l.p2-res[0])>0) swap(res[0],res[1]); res.pop_back(); } return res; } Polygon getCrossPointCC(Circle c1,Circle c2){ Polygon p(2); double d=abs(c1.c-c2.c); double a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d)); double t=arg(c2.c-c1.c); p[0]=c1.c+polar(c1.r,t+a); p[1]=c1.c+polar(c1.r,t-a); return p; } // IN:2 ON:1 OUT:0 int contains(Polygon g,Point p){ int n=g.size(); bool x=false; for(int i=0;ib.y) swap(a,b); if(a.y < EPS && EPS < b.y && cross(a,b) > EPS ) x = !x; } return (x?2:0); } Polygon andrewScan(Polygon s){ Polygon u,l; if(s.size()<3) return s; sort(s.begin(),s.end()); u.push_back(s[0]); u.push_back(s[1]); l.push_back(s[s.size()-1]); l.push_back(s[s.size()-2]); for(int i=2;i<(int)s.size();i++){ for(int n=u.size();n>=2&&ccw(u[n-2],u[n-1],s[i])!=CCW_CLOCKWISE;n--){ u.pop_back(); } u.push_back(s[i]); } for(int i=s.size()-3;i>=0;i--){ for(int n=l.size();n>=2&&ccw(l[n-2],l[n-1],s[i])!=CCW_CLOCKWISE;n--){ l.pop_back(); } l.push_back(s[i]); } reverse(l.begin(),l.end()); for(int i=u.size()-2;i>=1;i--) l.push_back(u[i]); return l; } Polygon convex_hull(Polygon ps){ int n=ps.size(); sort(ps.begin(),ps.end(),sort_y); int k=0; Polygon qs(n*2); for(int i=0;i1&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<0) k--; qs[k++]=ps[i]; } for(int i=n-2,t=k;i>=0;i--){ while(k>t&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<0) k--; qs[k++]=ps[i]; } qs.resize(k-1); return qs; } double diameter(Polygon s){ Polygon p=s; int n=p.size(); if(n==2) return abs(p[0]-p[1]); int i=0,j=0; for(int k=0;k0) swap(p[0],p[1]); return Line(p[0],p[1]); } Vector translate(Vector v,double theta){ Vector res; res.x=cos(theta)*v.x-sin(theta)*v.y; res.y=sin(theta)*v.x+cos(theta)*v.y; return res; } vector corner(Line l1,Line l2){ vector res; if(isParallel(l1,l2)){ double d=getDistanceLP(l1,l2.p1)/2.0; Vector v1=l1.p2-l1.p1; v1=v1/v1.abs()*d; Point p=l2.p1+translate(v1,90.0*(PI/180.0)); double d1=getDistanceLP(l1,p); double d2=getDistanceLP(l2,p); if(abs(d1-d2)>d){ p=l2.p1+translate(v1,-90.0*(PI/180.0)); } res.push_back(Line(p,p+v1)); }else{ Point p=getCrossPointLL(l1,l2); Vector v1=l1.p2-l1.p1,v2=l2.p2-l2.p1; v1=v1/v1.abs(); v2=v2/v2.abs(); res.push_back(Line(p,p+(v1+v2))); res.push_back(Line(p,p+translate(v1+v2,90.0*(PI/180.0)))); } return res; } Polygon tangent(Circle c1,Point p2){ Circle c2=Circle(p2,sqrt(norm(c1.c-p2)-c1.r*c1.r)); Polygon p=getCrossPointCC(c1,c2); sort(p.begin(),p.end()); return p; } vector tangent(Circle c1,Circle c2){ vector ls; if(c1.r=-1;s-=2){ double h=(c1.r+s*c2.r)/sqrt(g); if(equals(1-h*h,0)){ ls.emplace_back(c1.c+u*c1.r,c1.c+(u+v)*c1.r); }else if(1-h*h>0){ Point uu=u*h,vv=v*sqrt(1-h*h); ls.emplace_back(c1.c+(uu+vv)*c1.r,c2.c-(uu+vv)*c2.r*s); ls.emplace_back(c1.c+(uu-vv)*c1.r,c2.c-(uu-vv)*c2.r*s); } } return ls; } double closest_pair(Polygon &a,int l=0,int r=-1){ if(r<0){ r=a.size(); sort(a.begin(),a.end(),sort_x); } if(r-l<=1) return abs(a[0]-a[1]); int m=(l+r)>>1; double x=a[m].x; double d=min(closest_pair(a,l,m),closest_pair(a,m,r)); inplace_merge(a.begin()+l,a.begin()+m,a.begin()+r,sort_y); Polygon b; for(int i=l;i=d) continue; for(int j=0;j<(int)b.size();j++){ double dy=a[i].y-next(b.rbegin(),j)->y; if(dy>=d) break; d=min(d,abs(a[i]-*next(b.rbegin(),j))); } b.emplace_back(a[i]); } return d; } vector > > segmentArrangement(vector &ss, Polygon &ps){ int n=ss.size(); for(int i=0;i > > G(ps.size()); for(int i=0;i > ls; for(int j=0;j<(int)ps.size();j++) if(getDistanceSP(ss[i],ps[j]) ss,const int INF){ const int BTM = 0; const int LFT = 1; const int RGH = 2; const int TOP = 3; int n=ss.size(); vector ep; for(int i=0;iss[i].p2.x) swap(ss[i].p1,ss[i].p2); ep.emplace_back(ss[i].p1,i,LFT); ep.emplace_back(ss[i].p2,i,RGH); }else{ if(ss[i].p1.y>ss[i].p2.y) swap(ss[i].p1,ss[i].p2); ep.emplace_back(ss[i].p1,i,BTM); ep.emplace_back(ss[i].p2,i,TOP); } } sort(ep.begin(),ep.end()); set bt; bt.insert(INF); int cnt=0; for(int i=0;i dfs= [&](Circle c,Point a,Point b){ Vector va=c.c-a,vb=c.c-b; double f=cross(va,vb),res=0; if(equals(f,0.0)) return res; if(max(abs(va),abs(vb))c.r-EPS) return c.r*c.r*atan2(d.y,d.x); auto u=getCrossPointCS(c,Segment(a,b)); if(u.empty()) return res; if(u.size()>1u&&dot(u[1]-u[0],a-u[0])>0) swap(u[0],u[1]); u.emplace(u.begin(),a); u.emplace_back(b); for(int i=1;i<(int)u.size();i++) res+=dfs(c,u[i-1],u[i]); return res; }; double res=0; for(int i=0;i<(int)ps.size();i++) res+=dfs(c,ps[i],ps[(i+1)%ps.size()]); return res/2; } struct QuickFind{ int n; vector r,p; vector > v; QuickFind(){} QuickFind(int sz):n(sz),r(sz),p(sz),v(sz){ for(int i=0;i>n; if(n==0){ cout<<1<>ps; auto hs=[](Point p){return (int)((p.y+10000)*30000+(p.x+10000));}; unordered_map idx; for(int i=0;i100) continue; Point t=ps[i]+Vector(a,b); if(idx.count(hs(t))) qf.unite(i,idx[hs(t)]); } } } double ans=0; for(int i=0;i