1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 using namespace std;
  7 const double eps=1e-8;
  8 const double INF=1e20;
  9 const double PI=acos(-1.0);
 10 const int maxp=1010;
 11 int sgn(double x){
 12     if(fabs(x)<eps) return 0;
 13     if(x<0) return -1;
 14     else return 1;
 15 }
 16 inline double sqr(double x){return x*x;}
 17 struct Point{
 18     double x,y;
 19     Point(){}
 20     Point(double _x,double _y){
 21         x=_x;
 22         y=_y;
 23     }
 24     void input(){
 25         scanf("%lf %lf",&x,&y);
 26     }
 27     void output(){
 28         printf("%.2f %.2f\n",x,y);
 29     }
 30     bool operator == (const Point &b)const{
 31         return sgn(x-b.x) == 0 && sgn(y-b.y)== 0;
 32     }
 33     bool operator < (const Point &b)const{
 34         return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;
 35     }
 36     Point operator - (const Point &b)const{
 37         return Point(x-b.x,y-b.y);
 38     }
 39     //叉积
 40     double operator ^ (const Point &b)const{
 41         return x*b.y-y*b.x;
 42     }
 43     //点积
 44     double operator * (const Point &b)const{
 45         return x*b.x+y*b.y;
 46     }
 47     //返回长度
 48     double len(){
 49         return hypot(x,y);
 50     }
 51     //返回长度的平方
 52     double len2(){
 53         return x*x+y*y;
 54     }
 55     //返回两点的距离
 56     double distance(Point p){
 57         return hypot(x-p.x,y-p.y);
 58     }
 59     Point operator + (const Point &b)const{
 60         return Point(x+b.x,y+b.y);
 61     }
 62     Point operator * (const double &k)const{
 63         return Point(x*k,y*k);
 64     }
 65     Point operator / (const double &k)const{
 66         return Point(x/k,y/k);
 67     }
 68 
 69     //计算pa和pb的夹角
 70     //就是求这个点看a,b所成的夹角
 71     ///LightOJ1202
 72     double rad(Point a,Point b){
 73         Point p=*this;
 74         return fabs(atan2(fabs((a-p)^(b-p)),(a-p)*(b-p)));
 75     }
 76     //化为长度为r的向量
 77     Point trunc(double r){
 78         double l=len();
 79         if(!sgn(l)) return *this;
 80         r/=l;
 81         return Point(x*r,y*r);
 82     }
 83     //逆时针转90度
 84     Point rotleft(){
 85         return Point(-y,x);
 86     }
 87     //顺时针转90度
 88     Point rotright(){
 89         return Point(y,-x);
 90     }
 91     //绕着p点逆时针旋转angle
 92     Point rotate(Point p,double angle){
 93         Point v=(*this) -p;
 94         double c=cos(angle),s=sin(angle);
 95         return Point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
 96     }
 97 };
 98 
 99 struct Line{
100     Point s,e;
101     Line(){}
102     Line(Point _s,Point _e){
103         s=_s;
104         e=_e;
105     }
106     bool operator==(Line v){
107         return (s==v.s)&&(e==v.e);
108     }
109     //根据一个点和倾斜角angle确定直线，0<=angle<pi
110     Line(Point p,double angle){
111         s=p;
112         if(sgn(angle-PI/2)==0){
113             e=(s+Point(0,1));
114         }
115         else{
116             e=(s+Point(1,tan(angle)));
117         }
118     }
119     //ax+by+c=0;
120     Line(double a,double b,double c){
121         if(sgn(a)==0){
122             s=Point(0,-c/b);
123             e=Point(1,-c/b);
124         }
125         else if(sgn(b)==0){
126             s=Point(-c/a,0);
127             e=Point(-c/a,1);
128         }
129         else{
130             s=Point(0,-c/b);
131             e=Point(1,(-c-a)/b);
132         }
133     }
134     void input(){
135         s.input();
136         e.input();
137     }
138     void adjust(){
139         if(e<s) swap(s,e);
140     }
141     //求线段长度
142     double length(){
143         return s.distance(e);
144     }
145     //返回直线倾斜角 0<=angle<pi
146     double angle(){
147         double k=atan2(e.y-s.y,e.x-s.x);
148         if(sgn(k)<0) k+=PI;
149         if(sgn(k-PI)==0) k-=PI;
150         return k;
151     }
152     //点和直线的关系
153     //1 在左侧
154     //2 在右侧
155     //3 在直线上
156     int relation(Point p){
157         int c=sgn((p-s)^(e-s));
158         if(c<0) return 1;
159         else if(c>0) return 2;
160         else return 3;
161     }
162     //点在线段上的判断
163     bool pointonseg(Point p){
164         return sgn((p-s)^(e-s))==0&&sgn((p-s)*(p-e))<=0;
165     }
166     //两向量平行(对应直线平行或重合)
167     bool parallel(Line v){
168         return sgn((e-s)^(v.e-v.s))==0;
169     }
170     //两线段相交判断
171     //2 规范相交
172     //1 非规范相交
173     //0 不相交
174     int segcrossseg(Line v){
175         int d1=sgn((e-s)^(v.s-s));
176         int d2=sgn((e-s)^(v.e-s));
177         int d3=sgn((v.e-v.s)^(s-v.s));
178         int d4=sgn((v.e-v.s)^(e-v.s));
179         if((d1^d2)==-2&&(d3^d4)==-2) return 2;
180         return (d1==0&&sgn((v.s-s)*(v.s-e))<=0||
181                 d2==0&&sgn((v.e-s)*(v.e-e))<=0||
182                 d3==0&&sgn((s-v.s)*(s-v.e))<=0||
183                 d4==0&&sgn((e-v.s)*(e-v.e))<=0);
184     }
185     //直线和线段相交判断
186     //-*this line -v seg
187     //2 规范相交
188     //1 非规范相交
189     //0 不相交
190     int linecrossseg(Line v){
191         int d1=sgn((e-s)^(v.s-s));
192         int d2=sgn((e-s)^(v.e-s));
193         if((d1^d2)==-2) return 2;
194         return (d1==0||d2==0);
195     }
196     //两直线关系
197     //0 平行
198     //1 重合
199     //2 相交
200     int linecrossline(Line v){
201         if((*this).parallel(v))
202             return v.relation(s)==3;
203         return 2;
204     }
205     //求两直线的交点
206     //要保证两直线不平行或重合
207     Point crosspoint(Line v){
208         double a1=(v.e-v.s)^(s-v.s);
209         double a2=(v.e-v.s)^(e-v.s);
210         return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
211     }
212     //点到直线的距离
213     double dispointtoline(Point p){
214         return fabs((p-s)^(e-s))/length();
215     }
216     //点到线段的距离
217     double dispointtoseg(Point p){
218         if(sgn((p-s)*(e-s))<0||sgn((p-e)*(s-e))<0)
219             return min(p.distance(s),p.distance(e));
220         return dispointtoline(p);
221     }
222     //返回线段到线段的距离
223     //前提是两线段不相交，相交距离就是0了
224     double dissegtoseg(Line v){
225         return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));
226     }
227     //返回点P在直线上的投影
228     Point lineprog(Point p){
229         return s+(((e-s)*((e-s)*(p-s)))/((e-s).len2()));
230     }
231     //返回点P关于直线的对称点
232     Point symmetrypoint(Point p){
233         Point q=lineprog(p);
234         return Point(2*q.x-p.x,2*q.y-p.y);
235     }
236 };
237 
238 struct circle{
239     Point p;
240     double r;
241     circle(){}
242     circle(Point _p,double _r){
243         p=_p;
244         r=_r;
245     }
246 
247     circle(double x,double y,double _r){
248         p=Point(x,y);
249         r=_r;
250     }
251 
252     circle(Point a,Point b,Point c){///三角形的外接圆
253         Line u=Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
254         Line v=Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
255         p=u.crosspoint(v);
256         r=p.distance(a);
257     }
258 
259     circle(Point a,Point b,Point c,bool t){///三角形的内切圆
260         Line u,v;
261         double m=atan2(b.y-a.y,b.x-a.x),n=atan2(c.y-a.y,c.x-a.x);
262         u.s=a;
263         u.e=u.s+Point(cos((n+m)/2),sin((n+m)/2));
264         v.s=b;
265         m=atan2(a.y-b.y,a.x-b.x),n=atan2(c.y-b.y,c.x-b.x);
266         v.e=v.s+Point(cos((n+m)/2),sin((n+m)/2));
267         p=u.crosspoint(v);
268         r=Line(a,b).dispointtoseg(p);
269     }
270 
271     void input(){
272         p.input();
273         scanf("%lf",&r);
274     }
275 
276     void output(){
277         printf("%.2f %.2f %.2f\n",p.x,p.y,r);
278     }
279 
280     bool operator==(circle v){
281         return (p==v.p)&&sgn(r-v.r)==0;
282     }
283 
284     bool operator<(circle v)const{
285         return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));
286     }
287 
288     double area(){
289         return PI*r*r;
290     }
291 
292     double circumference(){ ///周长
293         return 2*PI*r;
294     }
295 
296     int relation(Point b){///点和圆的关系  0圆外  1圆上  2圆内
297         double dst=b.distance(p);
298         if(sgn(dst-r)<0) return 2;
299         else if(sgn(dst-r)==0) return 1;
300         return 0;
301     }
302 
303     int relationseg(Line v){///线段和圆的关系，比较的是圆心到线段的距离和半径的关系
304         double dst=v.dispointtoseg(p);
305         if(sgn(dst-r)<0) return 2;
306         else if(sgn(dst-r)==0) return 1;
307         return 0;
308     }
309 
310     int relationline(Line v){///直线和圆的关系，比较的是圆心到直线的距离和半径的关系
311         double dst=v.dispointtoline(p);
312         if(sgn(dst-r)<0) return 2;
313         else if(sgn(dst-r)==0) return 1;
314         return 0;
315     }
316 
317     int relationcircle(circle v){///两圆的关系  5相离 4外切 3相交 2内切 1内含
318         double d=p.distance(v.p);
319         if(sgn(d-r-v.r)>0) return 5;
320         if(sgn(d-r-v.r)==0) return 4;
321         double l=fabs(r-v.r);
322         if(sgn(d-r-v.r)<0&&sgn(d-l)>0) return 3;
323         if(sgn(d-l)==0) return 2;
324         if(sgn(d-l)<0)  return 1;
325     }
326 
327     int pointcrosscircle(circle v,Point &p1,Point &p2){///求两个圆的交点，0没有交点 1一个交点 2两个交点
328         int rel=relationcircle(v);
329         if(rel == 1 || rel == 5) return 0;
330         double d=p.distance(v.p);
331         double l=(d*d+r*r-v.r*v.r)/2*d;
332         double h=sqrt(r*r-l*l);
333         Point tmp=p+(v.p-p).trunc(l);
334         p1=tmp+((v.p-p).rotleft().trunc(h));
335         p2=tmp+((v.p-p).rotright().trunc(h));
336         if(rel == 2 || rel == 4) return 1;
337         return 2;
338     }
339 
340     int pointcrossline(Line v,Point &p1,Point &p2){///求直线和圆的交点，返回交点的个数
341         if(!(*this).relationline(v)) return 0;
342         Point a=v.lineprog(p);
343         double d=v.dispointtoline(p);
344         d=sqrt(r*r-d*d);
345         if(sgn(d)==0) {
346             p1=a;
347             p2=a;
348             return 1;
349         }
350         p1=a+(v.e-v.s).trunc(d);
351         p2=a-(v.e-v.s).trunc(d);
352         return 2;
353     }
354 
355     int getcircle(Point a,Point b,double r1,circle &c1,circle &c2){///得到过a，b两点，半径为r1的两个圆
356         circle x(a,r1),y(b,r1);
357         int t=x.pointcrosscircle(y,c1.p,c2.p);
358         if(!t) return 0;
359         c1.r=c2.r=r;
360         return t;
361     }
362 
363     int getcircle(Line u,Point q,double r1,circle &c1,circle &c2){///得到与直线u相切，过点q，半径为r1的圆
364         double dis = u.dispointtoline(q);
365         if(sgn(dis-r1*2)>0) return 0;
366         if(sgn(dis)==0) {
367             c1.p=q+((u.e-u.s).rotleft().trunc(r1));
368             c2.p=q+((u.e-u.s).rotright().trunc(r1));
369             c1.r=c2.r=r1;
370             return 2;
371         }
372         Line u1=Line((u.s+(u.e-u.s).rotleft().trunc(r1)),(u.e+(u.e-u.s).rotleft().trunc(r1)));
373         Line u2=Line((u.s+(u.e-u.s).rotright().trunc(r1)),(u.e+(u.e-u.s).rotright().trunc(r1)));
374         circle cc=circle(q,r1);
375         Point p1,p2;
376         if(!cc.pointcrossline(u1,p1,p2)) cc.pointcrossline(u2,p1,p2);
377         c1=circle(p1,r1);
378         if(p1==p2){
379             c2=c1;
380             return 1;
381         }
382         c2=circle(p2,r1);
383         return 2;
384     }
385 
386     int getcircle(Line u,Line v,double r1,circle &c1,circle &c2,circle &c3,circle &c4){///同时与直线u，v相切，半径为r1的圆
387         if(u.parallel(v)) return 0;///两直线平行
388         Line u1=Line(u.s+(u.e-u.s).rotleft().trunc(r1),u.e+(u.e-u.s).rotleft().trunc(r1));
389         Line u2=Line(u.s+(u.e-u.s).rotright().trunc(r1),u.e+(u.e-u.s).rotright().trunc(r1));
390         Line v1=Line(v.s+(v.e-v.s).rotleft().trunc(r1),v.e+(v.e-v.s).rotleft().trunc(r1));
391         Line v2=Line(v.s+(v.e-v.s).rotright().trunc(r1),v.e+(v.e-v.s).rotright().trunc(r1));
392         c1.r=c2.r=c3.r=c4.r=r1;
393         c1.p=u1.crosspoint(v1);
394         c2.p=u1.crosspoint(v2);
395         c3.p=u2.crosspoint(v1);
396         c4.p=u2.crosspoint(v2);
397         return 4;
398     }
399 
400     int getcircle(circle cx,circle cy,double r1,circle &c1,circle &c2){///同时与不相交圆 cx,cy相切，半径为r1的圆
401         circle x(cx.p,r1+cx.r),y(cy.p,r1+cy.r);
402         int t=x.pointcrosscircle(y,c1.p,c2.p);
403         if(!t) return 0;
404         c1.r=c2.r=r1;
405         return t;
406     }
407 
408     int tangentline(Point q,Line &u,Line &v){///过一点作圆的切线（先判断点和圆的关系）
409         int x=relation(q);
410         if(x==2) return 0;
411         if(x==1){
412             u=Line(q,q+(q-p).rotleft());
413             v=u;
414             return 1;
415         }
416         double d=p.distance(q);
417         double l=r*r/d;
418         double h=sqrt(r*r-l*l);
419         u=Line(q,p+((q-p).trunc(l)+(q-p).rotleft().trunc(h)));
420         v=Line(q,p+((q-p).trunc(l)+(q-p).rotright().trunc(h)));
421         return 2;
422     }
423 
424     double areacircle(circle v){///求两圆相交的面积
425         int rel=relationcircle(v);
426         if(rel >= 4) return 0.0;
427         if(rel <= 2) return min(area(),v.area());
428         double d=p.distance(v.p);
429         double hf=(r+v.r+d)/2.0;
430         double ss=2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
431         double a1=acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
432         a1=a1*r*r;
433         double a2=acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
434         a2=a2*v.r*v.r;
435         return a1+a2-ss;
436     }
437 
438     double areatriangle(Point a,Point b){///求圆和三角形pab的相交面积
439         if(sgn((p-a)^(p-b))==0) return 0.0;
440         Point q[5];
441         int len=0;
442         q[len++]=a;
443         Line l(a,b);
444         Point p1,p2;
445         if(pointcrossline(l,q[1],q[2])==2){
446             if(sgn((a-q[1])*(b-q[1]))<0) q[len++]=q[1];
447             if(sgn((a-q[2])*(b-q[2]))<0) q[len++]=q[2];
448         }
449         q[len++]=b;
450         if(len==4 && sgn((q[0]-q[1])*(q[2]-q[1]))>0) swap(q[1],q[2]);
451         double res=0;
452         for(int i=0;i<len-1;i++){
453             if(relation(q[i])==0||relation(q[i+1])==0){
454                 double arg=p.rad(q[i],q[i+1]);
455                 res+=r*r*arg/2.0;
456             }
457             else{
458                 res+=fabs((q[i]-p)^(q[i+1]-p))/2.0;
459             }
460         }
461         return res;
462     }
463 };
464 
465 struct polygon{
466     int n;
467     Point p[1010];
468     Line l[1010];
469     void input(int _n){
470         n=_n;
471         for(int i=0;i<n;i++){
472             p[i].input();
473         }
474     }
475 
476     void add(Point q){
477         p[n++]=q;
478     }
479 
480     void getline(){
481         for(int i=0;i<n;i++){
482             l[i]=Line(p[i],p[(i+1)%n]);
483         }
484     }
485 
486     struct cmp{
487         Point p;
488         cmp(const Point &p0){p=p0;}
489         bool operator()(const Point &aa,const Point &bb){
490             Point a=aa,b=bb;
491             int d=sgn((a-p)^(b-p));
492             if(d==0){
493                 return sgn(a.distance(p)-b.distance(p))<0;
494             }
495             return d>0;
496         }
497     };
498 
499     void norm(){///进行极角排序
500         Point mi=p[0];
501         for(int i=1;i<n;i++){
502             mi=min(mi,p[i]);
503             sort(p,p+n,cmp(mi));
504         }
505     }
506 
507     void getconvex(polygon &convex){///得到第一种凸包的方法，编号为0～n-1，可能要特判所有点共点或共线的特殊情况
508         sort(p,p+n);
509         convex.n=n;
510         for(int i=0;i<min(n,2);i++){
511             convex.p[i]=p[i];
512         }
513         if(convex.n==2&&(convex.p[0]==convex.p[1])) convex.n--;
514         if(n<=2) return;
515         int &top=convex.n;
516         top=1;
517         for(int i=2;i<n;i++){
518             while(top&&sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<0) top--;
519             convex.p[++top]=p[i];
520         }
521         int temp=top;
522         convex.p[++top]=p[n-2];
523         for(int i=n-3;i>=0;i--){
524             while(top!=temp&&sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<=0) top--;
525             convex.p[++top]=p[i];
526         }
527         if(convex.n==2&&(convex.p[0]==convex.p[1])) convex.n--;
528         convex.norm();
529     }
530 
531     void Graham(polygon &convex){///得到凸包的第二种方法
532         norm();
533         int &top=convex.n;
534         top=0;
535         if(n==1){
536             top=1;
537             convex.p[0]=p[0];
538             return;
539         }
540         if(n==2){
541             top=2;
542             convex.p[0]=p[0];
543             convex.p[1]=p[1];
544             if(convex.p[0]==convex.p[1]) top--;
545             return;
546         }
547         convex.p[0]=p[0];
548         convex.p[1]=p[1];
549         top=2;
550         for(int i=2;i<n;i++){
551             while(top>1&&sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2]))<=0) top--;
552             convex.p[top++]=p[i];
553         }
554         if(convex.n==2 && (convex.p[0]==convex.p[1])) convex.n--;
555     }
556 
557     bool inconvex(){///判断是不是凸的
558         bool s[3];
559         memset(s,false,sizeof(s));
560         for(int i=0;i<n;i++){
561             int j=(i+1)%n;
562             int k=(j+1)%n;
563             s[sgn((p[j]-p[i])^(p[k]-p[i]))+1]=true;
564             if(s[0]&&s[2]) return false;
565         }
566         return true;
567     }
568 
569     int relationpoint(Point q){///判断点和任意多边形的关系  3点上 2边上 1内部 0外部
570         for(int i=0;i<n;i++){
571             if(p[i]==q) return 3;
572         }
573         getline();
574         for(int i=0;i<n;i++){
575             if(l[i].pointonseg(q)) return 2;
576         }
577         int cnt=0;
578         for(int i=0;i<n;i++){
579             int j=(i+1)%n;
580             int k=sgn((q-p[j])^(p[i]-p[j]));
581             int u=sgn(p[i].y-q.y);
582             int v=sgn(p[j].y-q.y);
583             if(k>0&&u<0&&v>=0) cnt++;
584             if(k<0&&v<0&&u>=0) cnt--;
585         }
586         return cnt!=0;
587     }
588 
589     void convexcnt(Line u,polygon &po){///直线u切割凸多边形左侧  注意直线方向
590         int &top=po.n;
591         top=0;
592         for(int i=0;i<n;i++){
593             int d1=sgn((u.e-u.s)^(p[i]-u.s));
594             int d2=sgn((u.e-u.s)^(p[(i+1)%n]-u.s));
595             if(d1>=0) po.p[top++]=p[i];
596             if(d1*d2<0)po.p[top++]=u.crosspoint(Line(p[i],p[(i+1)%n]));
597         }
598     }
599 
600     double getcircumference(){///得到周长
601         double sum=0;
602         for(int i=0;i<n;i++){
603             sum+=p[i].distance(p[(i+1)%n]);
604         }
605         return sum;
606     }
607 
608     double getarea(){///得到面积
609         double sum=0;
610         for(int i=0;i<n;i++){
611             sum+=(p[i]^p[(i+1)%n]);
612         }
613         return fabs(sum)/2;
614     }
615 
616     bool getdir(){///得到方向 1表示逆时针  0表示顺时针
617         double sum=0;
618         for(int i=0;i<n;i++){
619             sum+=(p[i]^p[(i+1)%n]);
620         }
621         if(sgn(sum)>0) return 1;
622         return 0;
623     }
624 
625     Point getbarycentre(){///得到重心
626         Point ret(0,0);
627         double area=0;
628         for(int i=1;i<n-1;i++){
629             double tmp=(p[i]-p[0])^(p[i+1]-p[0]);
630             if(sgn(tmp)==0) continue;
631             area+=tmp;
632             ret.x+=(p[0].x+p[i].x+p[i+1].x)/3*tmp;
633             ret.y+=(p[0].y+p[i].y+p[i+1].y)/3*tmp;
634         }
635         if(sgn(area)) ret =ret/area;
636         return ret;
637     }
638 
639     double areacircle(circle c){///多边形和圆交的面积
640         double ans=0;
641         for(int i=0;i<n;i++){
642             int j=(i+1)%n;
643             if(sgn((p[j]-c.p)^(p[i]-c.p))>=0) ans+=c.areatriangle(p[i],p[j]);
644             else ans-=c.areatriangle(p[i],p[j]);
645         }
646         return fabs(ans);
647     }
648 
649     int relationcircle(circle c){///多边形和圆的关系 2圆完全在多边形内  1圆在多边形里面，碰到了多边形的边界  0其他
650         getline();
651         int x=2;
652         if(relationpoint(c.p)!=1) return 0;
653         for(int i=0;i<n;i++){
654             if(c.relationseg(l[i])==2) return 0;
655             if(c.relationseg(l[i])==1) x=1;
656         }
657         return x;
658     }
659 };
660 
661 double cross(Point a,Point b,Point c){///ab x ac
662     return (b-a)^(c-a);
663 }
664 
665 double dot(Point a,Point b,Point c){///ab*ac;
666     return (b-a)*(c-a);
667 }
668 
669 /*double minRectangleCover(polygon A){///最小矩形面积覆盖  A必须是凸包
670     if(A.n<3) return 0.0;
671     A.p[A.n]==A.p[0];
672     double ans=-1;
673     int r=1,p=1,q;
674     for(int i=0;i<A.n;i++){
675 
676     }
677 }*/
678 
679 vector<Point> convexCut(const vector<Point>&ps,Point q1,Point q2){///直线切凸多边形，多边形是逆时针的，在q1q2的左侧
680     vector<Point>qs;
681     int n=ps.size();
682     for(int i=0;i<n;i++){
683         Point p1=ps[i],p2=ps[(i+1)%n];
684         int d1=sgn((q2-q1)^(p1-q1)),d2=sgn((q2-q1)^(p2-q1));
685         if(d1>=0) qs.push_back(p1);
686         if(d1*d2<0) qs.push_back(Line(p1,p2).crosspoint(Line(q1,q2)));
687     }
688     return qs;
689 }
690 
691 struct halfplane:public Line{
692     double angle;
693     halfplane(){}
694     halfplane(Point _s,Point _e){///表示向量s->e逆时针（左侧）的半平面
695         s=_s;
696         e=_e;
697     }
698     halfplane(Line v){
699         s=v.s;
700         e=v.e;
701     }
702     void calcangle(){
703         angle=atan2(e.y-s.y,e.x-s.x);
704     }
705     bool operator<(const halfplane &b)const{
706         return angle<b.angle;
707     }
708 };
709 
710 struct halfplanes{
711     int n;
712     halfplane hp[2020];
713     Point p[2020];
714     int que[2020];
715     int st,ed;
716     void push(halfplane tmp){
717         hp[n++]=tmp;
718     }
719 
720     void unique(){///去重
721         int m=1;
722         for(int i=1;i<n;i++){
723             if(sgn(hp[i].angle-hp[i-1].angle)!=0) hp[m++]=hp[i];
724             else if(sgn((hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s))>0) hp[m-1]=hp[i];
725         }
726         n=m;
727     }
728     bool halfplaneinsert(){
729         for(int i=0;i<n;i++) hp[i].calcangle();
730         sort(hp,hp+n);
731         unique();
732         que[st=0]=0;
733         que[ed=1]=1;
734         p[1]=hp[0].crosspoint(hp[1]);
735         for(int i=2;i<n;i++){
736             while(st<ed&&sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0) ed--;
737             while(st<ed&&sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0) st++;
738             que[++ed]=i;
739             if(hp[i].parallel(hp[que[ed-1]])) return false;
740             p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
741         }
742         while(st<ed&&sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0) ed--;
743         while(st<ed&&sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0) st++;
744         if(st+1>=ed) return false;
745         return true;
746     }
747 
748     void getconvex(polygon &con){///得到最后半平面交得到的凸多边形，要先调用halfplaneinsert()且返回true
749         p[st]=hp[que[st]].crosspoint(hp[que[ed]]);
750         con.n=ed-st+1;
751         for(int j=st,i=0;j<=ed;i++,j++){
752             con.p[i]=p[j];
753         }
754     }
755 };
756 
757 struct circles{
758     circle c[1010];
759     double ans[1010];///ans[i]表示被覆盖了i次的面积
760     double pre[1010];
761     int n;
762     circles(){}
763     void add(circle cc){
764         c[n++]=cc;
765     }
766 
767     bool inner(circle x,circle y){///x包含在y中
768         if(x.relationcircle(y)!=1) return 0;
769         return sgn(x.r-y.r)<=0?1:0;
770     }
771 
772     void init_or(){///圆的面积并去掉内含的圆
773         bool mark[1010]={0};
774         int i,j,k=0;
775         for(i=0;i<n;i++){
776             for(j=0;j<n;j++){
777                 if(i!=j&&!mark[j]){
778                     if(c[i]==c[j]||inner(c[i],c[j])) break;
779                 }
780             }
781             if(j<n) mark[i]=1;
782         }
783         for(i=0;i<n;i++){
784             if(!mark[i]) c[k++]=c[i];
785         }
786         n=k;
787     }
788 
789     void init_add(){///圆的面积交去掉内含的圆
790         int i,j,k;
791         bool mark[1010]={0};
792         for(i=0;i<n;i++){
793             for(int j=0;j<n;j++){
794                 if(i!=j&&!mark[j]){
795                     if((c[i]==c[j])||inner(c[j],c[i])) break;
796                 }
797             }
798             if(j<n) mark[i]=1;
799         }
800         for(i=0;i<n;i++){
801             if(!mark[i]){
802                 c[k++]=c[i];
803             }
804         }
805         n=k;
806     }
807 
808     double areaarc(double th,double r){///半径为r的圆，弧度为th，对应的弓形的面积
809         return 0.5*r*r*(th-sin(th));
810     }
811 
812 
813     void getarea(){
814         memset(ans,0,sizeof(ans));
815         vector<pair<double,int> >v;
816         for(int i=0;i<n;i++){
817             v.clear();
818             v.push_back(make_pair(-PI,1));
819             v.push_back(make_pair(PI,-1));
820             for(int j=0;j<n;j++){
821                 if(i!=j){
822                     Point q=(c[j].p-c[i].p);
823                     double ab=q.len(),ac=c[i].r,bc=c[j].r;
824                     if(sgn(ab+ac-bc)<=0){
825                         v.push_back(make_pair(-PI,1));
826                         v.push_back(make_pair(PI,-1));
827                         continue;
828                     }
829                     if(sgn(ab+bc-ac)<=0)continue;
830                     if(sgn(ab-ac-bc)>0) continue;
831                     double th=atan2(q.y,q.x),fai=acos((ac*ac+ab*ab-bc*bc)/(2.0*ac*ab));
832                     double a0=th-fai;
833                     if(sgn(a0+PI)<0) a0+=2*PI;
834                     double a1=th+fai;
835                     if(sgn(a1-PI)>0) a1-=2*PI;
836                     if(sgn(a0-a1)>0){
837                         v.push_back(make_pair(a0,1));
838                         v.push_back(make_pair(PI,-1));
839                         v.push_back(make_pair(-PI,1));
840                         v.push_back(make_pair(a1,-1));
841                     }
842                     else{
843                         v.push_back(make_pair(a0,1));
844                         v.push_back(make_pair(a1,-1));
845                     }
846                 }
847                 sort(v.begin(),v.end());
848                 int cur=0;
849                 for(int j=0;j<v.size();j++){
850                     if(cur&&sgn(v[j].first-pre[cur])){
851                         ans[cur]+=areaarc(v[j].first-pre[cur],c[i].r);
852                         ans[cur]+=0.5*(Point(c[i].p.x+c[i].r*cos(pre[cur]),c[i].p.y+c[i].r*sin(pre[cur]))^Point(c[i].p.x+c[i].r*cos(v[j].first),c[i].p.y+c[i].r*sin(v[j].first)));
853                     }
854                     cur+=v[j].second;
855                     pre[cur]=v[j].first;
856                 }
857             }
858         }
859         for(int i=1;i<n;i++){
860             ans[i]-=ans[i+1];
861         }
862     }
863 };
864 
865 
866 bool Check(Line a,Line b){
867     if(sgn((a.s-a.e)^(b.s-a.e))*sgn((a.s-a.e)^(b.e-a.e))>0) return false;
868     if(sgn((b.s-b.e)^(a.s-b.e))*sgn((b.s-b.e)^(a.e-b.e))>0) return false;
869     if(sgn(max(a.s.x,a.e.x)-min(b.s.x,b.e.x))>=0&&sgn(max(b.s.x,b.e.x)-min(a.s.x,a.e.x))>=0
870      &&sgn(max(a.s.y,a.e.y)-min(b.s.y,b.e.y))>=0&&sgn(max(b.s.y,b.e.y)-min(a.s.y,a.e.y))>=0)
871         return true;
872     else return false;
873 }
874 
875 Line L[2005];
876 
877 int main(){
878     int t;
879     scanf("%d",&t);
880     Point p;
881     for(int Case=1;Case<=t;Case++){
882         double r;
883         int n;
884         scanf("%lf %d",&r,&n);
885         polygon poly;
886         halfplane hp;
887         halfplanes hps;
888         hps.n=0;
889         hp.s.x=r,hp.s.y=-r,hp.e.x=r,hp.e.y=r,hps.push(hp);
890         hp.s.x=r,hp.s.y=r,hp.e.x=-r,hp.e.y=r,hps.push(hp);
891         hp.s.x=-r,hp.s.y=r,hp.e.x=-r,hp.e.y=-r,hps.push(hp);
892         hp.s.x=-r,hp.s.y=-r,hp.e.x=r,hp.e.y=-r,hps.push(hp);
893         for(int i=1;i<=n;i++){
894             L[i].input();
895         }
896         p.input();
897         for(int i=1;i<=n;i++){
898             if(cross(L[i].s,p,L[i].e)>=0){
899                 swap(L[i].s,L[i].e);
900             }
901             hp.s=L[i].s,hp.e=L[i].e;
902             hps.push(hp);
903         }
904         if(hps.halfplaneinsert()){
905             hps.getconvex(poly);
906         }
907         circle c(0,0,r);
908         double ans1=c.area();
909         double ans2=poly.areacircle(c);
910         printf("Case %d: %.5f%%\n",Case,ans2*100/ans1);
911     }
912     return 0;
913 }
914 /*
915 
916 5 1
917 -5 0 5 3
918 0 0
919 
920 5 2
921 -5 0 5 3
922 -5 0 5 -3
923 0 0
924 
925 5 2
926 -5 0 5 3
927 -5 0 5 -3
928 0 4.9
929 
930 5 2
931 -5 0 5 3
932 -5 0 5 -3
933 0 -4.9
934 
935 1.00 2
936 -1.00 0.00 1.00 0.00
937 0.00 -1.00 0.00 1.00
938 0.50 0.50
939 
940 1.00 1
941 -1.00 0.00 1.00 0.00
942 0.50 0.50
943 
944 */