#include #include #include #define LD double #define LL long long #define Re register int #define Vector Point using namespace std; const int N=262144+3; const LD eps=1e-8,Pi=acos(-1.0); inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}// 撤销操作 inline LD Abs(LD a){return a*dcmp(a);} struct Point{ LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;} inline void in(){scanf("%lf%lf",&x,&y);} inline void out(){printf("%.2lf %.2lf\n",x,y);} }; inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;} inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;} inline LD Len(Vector a){return sqrt(Dot(a,a));} inline LD Angle(Vector a,Vector b){return acos(Dot(a,b)/Len(a)/Len(b));}// 撤销操作�нǡ� inline Vector Normal(Vector a){return Vector(-a.y,a.x);} inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);} inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);} inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);} inline bool operator==(Point a,Point b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);} inline Point turn_P(Point a,LD theta){ LD x=a.x*cos(theta)+a.y*sin(theta); LD y=-a.x*sin(theta)+a.y*cos(theta); return Point(x,y); } inline Point turn_PP(Point a,Point b,LD theta){ LD x=(a.x-b.x)*cos(theta)+(a.y-b.y)*sin(theta)+b.x; LD y=-(a.x-b.x)*sin(theta)+(a.y-b.y)*cos(theta)+b.y; return Point(x,y); } inline int pan_PL(Point p,Point a,Point b){ return !dcmp(Cro(p-a,b-a))&&dcmp(Dot(p-a,p-b))<=0; } inline LD dis_PL(Point p,Point a,Point b){ if(a==b)return Len(p-a);//AB�غ� Vector x=p-a,y=p-b,z=b-a; if(dcmp(Dot(x,z))<0)return Len(x); if(dcmp(Dot(y,z))>0)return Len(y); return Abs(Cro(x,z)/Len(z)); } inline int pan_PL_(Point p,Point a,Point b){ return !dcmp(Cro(p-a,b-a)); } inline Point FootPoint(Point p,Point a,Point b){ Vector x=p-a,y=p-b,z=b-a; LD len1=Dot(x,z)/Len(z),len2=-1.0*Dot(y,z)/Len(z); return a+z*(len1/(len1+len2)); } inline Point Symmetry_PL(Point p,Point a,Point b){ return p+(FootPoint(p,a,b)-p)*2; } inline Point cross_LL(Point a,Point b,Point c,Point d){ Vector x=b-a,y=d-c,z=a-c; return a+x*(Cro(y,z)/Cro(x,y)); } inline int pan_cross_L_L(Point a,Point b,Point c,Point d){ return pan_PL(cross_LL(a,b,c,d),c,d); } inline int pan_cross_LL(Point a,Point b,Point c,Point d){ LD c1=Cro(b-a,c-a),c2=Cro(b-a,d-a); LD d1=Cro(d-c,a-c),d2=Cro(d-c,b-c); return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0; } inline int PIP(Point *P,Re n,Point a){ Re cnt=0;LD tmp; for(Re i=1;i<=n;++i){ Re j=i=min(P[i].y,P[j].y)&&a.y0; } return cnt&1; } inline int judge(Point a,Point L,Point R){ return dcmp(Cro(L-a,R-a))>0; } inline int PIP_(Point *P,Re n,Point a){ if(judge(P[1],a,P[2])||judge(P[1],P[n],a))return 0; if(pan_PL(a,P[1],P[2])||pan_PL(a,P[1],P[n]))return 2; Re l=2,r=n-1; while(l>1; if(judge(P[1],P[mid],a))l=mid; else r=mid-1; } if(judge(P[l],a,P[l+1]))return 0; if(pan_PL(a,P[l],P[l+1]))return 2; return 1; } inline int judge_PP(Point *A,Re n,Point *B,Re m){ for(Re i1=1;i1<=n;++i1){ Re j1=i11&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t; cp[++t]=P[i]; } Re St=t; for(Re i=n-1;i>=1;--i){ while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t; cp[++t]=P[i]; } return --t; } struct Line{ Point a,b;LD k;Line(Point A=Point(0,0),Point B=Point(0,0)){a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);} inline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,a);} }L[N],Q[N]; inline Point cross(Line L1,Line L2){return cross_LL(L1.a,L1.b,L2.a,L2.b);} inline int judge(Line L,Point a){return dcmp(Cro(a-L.a,L.b-L.a))>0;} inline int halfcut(Line *L,Re n,Point *P){ sort(L+1,L+n+1);Re m=n;n=0; for(Re i=1;i<=m;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++n]=L[i]; Re h=1,t=0; for(Re i=1;i<=n;++i){ while(h0?V1[i++]:V2[j++]); while(i<=n)++t,V[t]=V[t-1]+V1[i++]; while(j<=m)++t,V[t]=V[t-1]+V2[j++]; return t; } #define S(a) ((a)*(a)) struct Circle{Point O;LD r;Circle(Point P,LD R=0){O=P,r=R;}}; inline Circle getCircle(Point A,Point B,Point C){ LD x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y; LD D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2)); LD E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1); LD F=-(S(x1)+S(y1)+D*x1+E*y1); return Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0)); } inline Circle getcircle(Point A,Point B,Point C){ Point P1=(A+B)*0.5,P2=(A+C)*0.5; Point O=cross_LL(P1,P1+Normal(B-A),P2,P2+Normal(C-A)); return Circle(O,Len(A-O)); } inline int PIC(Circle C,Point a){return dcmp(Len(a-C.O)-C.r)<=0;} inline void Random(Point *P,Re n){for(Re i=1;i<=n;++i)swap(P[i],P[rand()%n+1]);} inline Circle Min_Circle(Point *P,Re n){ // random_shuffle(P+1,P+n+1); Random(P,n);Circle C=Circle(P[1],0); for(Re i=2;i<=n;++i)if(!PIC(C,P[i])){ C=Circle(P[i],0); for(Re j=1;j0?1:-1;LD ans=0; Vector x=A-O,y=B-O; Re flag1=dcmp(Len(x)-R)>0,flag2=dcmp(Len(y)-R)>0; if(!flag1&&!flag2)ans=Abs(Cro(A-O,B-O))/2.0; else if(flag1&&flag2){ if(dcmp(dis_PL(O,A,B)-R)>=0)ans=R*R*Angle(x,y)/2.0; else{ if(dcmp(Cro(A-O,B-O))>0)swap(A,B); Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx); Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point B_=F+z,A_=F-z; ans=R*R*(Angle(A-O,A_-O)+Angle(B-O,B_-O))/2.0+Cro(B_-O,A_-O)/2.0; } } else{ if(flag1)swap(A,B); Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx); Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point C=dcmp(Cro(A-O,B-O))>0?F-z:F+z; ans=Abs(Cro(A-O,C-O))/2.0+R*R*Angle(C-O,B-O)/2.0; } return ans*op; } int main(){}