1 #include<vector>  2 #include<list>  3 #include<map>  4 #include<set>  5 #include<deque>  6 #include<queue>  7 #include<stack>  8 #include<bitset>  9 #include<algorithm> 10 #include<functional> 11 #include<numeric> 12 #include<utility> 13 #include<iostream> 14 #include<sstream> 15 #include<iomanip> 16 #include<cstdio> 17 #include<cmath> 18 #include<cstdlib> 19 #include<cctype> 20 #include<string> 21 #include<cstring> 22 #include<cstdio> 23 #include<cmath> 24 #include<cstdlib> 25 #include<ctime> 26 #include<climits> 27 #include<complex> 28 #define mp make_pair 29 #define pb push_back 30 using namespace std; 31 const double eps=1e-8;//精度 32 const double pi=acos(-1.0);//π 33 const double inf=1e20;//无穷大 34 const int maxp=1111;//最大点数 35 /* 36     判断d是否在精度内等于0 37 */ 38  39 bool cmp(double x,double y) 40 {    return x<y;    } 41  42 int dblcmp(double d) 43 { 44     if (fabs(d)<eps)return 0; 45     return d>eps?1:-1; 46 } 47 /* 48     求x的平方 49 */ 50 inline double sqr(double x){return x*x;} 51 /* 52     点/向量 53 */ 54 struct point 55 { 56     double x,y; 57     int dis;        //inside(1) OR outside(0) OF the continent 58     point(){} 59     point(double _x,double _y):x(_x),y(_y){}; 60     //读入一个点 61     void input() 62     { 63         scanf("%lf%lf",&x,&y); 64     } 65     //输出一个点 66     void output() 67     { 68         printf("%.2f %.2f\n",x,y); 69     } 70     //判断两点是否相等 71     bool operator==(point a)const 72     { 73         return dblcmp(a.x-x)==0&&dblcmp(a.y-y)==0; 74     } 75     //判断两点大小 76     bool operator<(point a)const 77     { 78         return dblcmp(a.x-x)==0?dblcmp(y-a.y)<0:x<a.x; 79     } 80     //点到源点的距离/向量的长度 81     double len() 82     { 83         return hypot(x,y); 84     } 85     //点到源点距离的平方 86     double len2() 87     { 88         return x*x+y*y; 89     } 90     //两点间的距离 91     double distance(point p) 92     { 93         return hypot(x-p.x,y-p.y); 94     } 95     //向量加 96     point add(point p) 97     { 98         return point(x+p.x,y+p.y); 99     }100     //向量减101     point sub(point p)102     {103         return point(x-p.x,y-p.y);104     }105     //向量乘106     point mul(double b)107     {108         return point(x*b,y*b);109     }110     //向量除111     point div(double b)112     {113         return point(x/b,y/b);114     }115     //点乘116     double dot(point p)117     {118         return x*p.x+y*p.y;119     }120     //叉乘121     double det(point p)122     {123         return x*p.y-y*p.x;124     }125     //XXXXXXX126     double rad(point a,point b)127     {128         point p=*this;129         return fabs(atan2(fabs(a.sub(p).det(b.sub(p))),a.sub(p).dot(b.sub(p))));130     }131     //截取长度r132     point trunc(double r)133     {134         double l=len();135         if (!dblcmp(l))return *this;136         r/=l;137         return point(x*r,y*r);138     }139     //左转90度140     point rotleft()141     {142         return point(-y,x);143     }144     //右转90度145     point rotright()146     {147         return point(y,-x);148     }149     //绕点p逆时针旋转angle角度150     point rotate(point p,double angle)151     {152         point v=this->sub(p);153         double c=cos(angle),s=sin(angle);154         return point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);155     }156 };157 /*158     线段/直线159 */160 struct line161 {162     point a,b;163     line(){}164     line(point _a,point _b)165     {166         a=_a;167         b=_b;168     }169     //判断线段相等170     bool operator==(line v)171     {172         return (a==v.a)&&(b==v.b);173     }174     //点p做倾斜角为angle的射线175     line(point p,double angle)176     {177         a=p;178         if (dblcmp(angle-pi/2)==0)179         {180             b=a.add(point(0,1));181         }182         else183         {184             b=a.add(point(1,tan(angle)));185         }186     }187     //直线一般式ax+by+c=0188     line(double _a,double _b,double _c)189     {190         if (dblcmp(_a)==0)191         {192             a=point(0,-_c/_b);193             b=point(1,-_c/_b);194         }195         else if (dblcmp(_b)==0)196         {197             a=point(-_c/_a,0);198             b=point(-_c/_a,1);199         }200         else201         {202             a=point(0,-_c/_b);203             b=point(1,(-_c-_a)/_b);204         }205     }206     //读入一个线段207     void input()208     {209         a.input();210         b.input();211     }212     //校准线段两点213     void adjust()214     {215         if (b<a)swap(a,b);216     }217     //线段长度218     double length()219     {220         return a.distance(b);221     }222     //直线倾斜角 0<=angle<180223     double angle()224     {225         double k=atan2(b.y-a.y,b.x-a.x);226         if (dblcmp(k)<0)k+=pi;227         if (dblcmp(k-pi)==0)k-=pi;228         return k;229     }230     //点和线段关系231     //1 在逆时针232     //2 在顺时针233     //3 平行234     int relation(point p)235     {236         int c=dblcmp(p.sub(a).det(b.sub(a)));237         if (c<0)return 1;238         if (c>0)return 2;239         return 3;240     }241     //点是否在线段上242     bool pointonseg(point p)243     {244         return dblcmp(p.sub(a).det(b.sub(a)))==0&&dblcmp(p.sub(a).dot(p.sub(b)))<=0;245     }246     //两线是否平行247     bool parallel(line v)248     {249         return dblcmp(b.sub(a).det(v.b.sub(v.a)))==0;250     }251     //线段和线段关系252     //0 不相交253     //1 非规范相交254     //2 规范相交255     int segcrossseg(line v)256     {257         int d1=dblcmp(b.sub(a).det(v.a.sub(a)));258         int d2=dblcmp(b.sub(a).det(v.b.sub(a)));259         int d3=dblcmp(v.b.sub(v.a).det(a.sub(v.a)));260         int d4=dblcmp(v.b.sub(v.a).det(b.sub(v.a)));261         if ((d1^d2)==-2&&(d3^d4)==-2)return 2;262         return (d1==0&&dblcmp(v.a.sub(a).dot(v.a.sub(b)))<=0||263                 d2==0&&dblcmp(v.b.sub(a).dot(v.b.sub(b)))<=0||264                 d3==0&&dblcmp(a.sub(v.a).dot(a.sub(v.b)))<=0||265                 d4==0&&dblcmp(b.sub(v.a).dot(b.sub(v.b)))<=0);266     }267     //线段和直线v关系268     int linecrossseg(line v)//*this seg v line269     {270         int d1=dblcmp(b.sub(a).det(v.a.sub(a)));271         int d2=dblcmp(b.sub(a).det(v.b.sub(a)));272         if ((d1^d2)==-2)return 2;273         return (d1==0||d2==0);274     }275     //直线和直线关系276     //0 平行277     //1 重合278     //2 相交279     int linecrossline(line v)280     {281         if ((*this).parallel(v))282         {283             return v.relation(a)==3;284         }285         return 2;286     }287     //求两线交点288     point crosspoint(line v)289     {290         double a1=v.b.sub(v.a).det(a.sub(v.a));291         double a2=v.b.sub(v.a).det(b.sub(v.a));292         return point((a.x*a2-b.x*a1)/(a2-a1),(a.y*a2-b.y*a1)/(a2-a1));293     }294     //点p到直线的距离295     double dispointtoline(point p)296     {297         return fabs(p.sub(a).det(b.sub(a)))/length();298     }299     //点p到线段的距离300     double dispointtoseg(point p)301     {302         if (dblcmp(p.sub(b).dot(a.sub(b)))<0||dblcmp(p.sub(a).dot(b.sub(a)))<0)303         {304             return min(p.distance(a),p.distance(b));305         }306         return dispointtoline(p);307     }308     //XXXXXXXX309     point lineprog(point p)310     {311         return a.add(b.sub(a).mul(b.sub(a).dot(p.sub(a))/b.sub(a).len2()));312     }313     //点p关于直线的对称点314     point symmetrypoint(point p)315     {316         point q=lineprog(p);317         return point(2*q.x-p.x,2*q.y-p.y);318     }319 };320 321 /*322     多边形323 */324 struct polygon325 {326     int n;//点个数327     point p[maxp];//顶点328     line l[maxp];//边329     //读入一个多边形330     void input()331     {332         for (int i=0;i<n;i++)333         {334             p[i].input();335         }336     }337     //添加一个点338     void add(point q)339     {340         p[n++]=q;341     }342     //取得边343     void getline()344     {345         for (int i=0;i<n;i++)346         {347             l[i]=line(p[i],p[(i+1)%n]);348         }349     }350     struct cmp351     {352         point p;353         cmp(const point &p0){p=p0;}354         bool operator()(const point &aa,const point &bb)355         {356             point a=aa,b=bb;357             int d=dblcmp(a.sub(p).det(b.sub(p)));358             if (d==0)359             {360                 return dblcmp(a.distance(p)-b.distance(p))<0;361             }362             return d>0;363         }364     };365     void norm()366     {367         point mi=p[0];368         for (int i=1;i<n;i++)mi=min(mi,p[i]);369         sort(p,p+n,cmp(mi));370     }371     //求凸包存入多边形convex372     void getconvex(polygon &convex)373     {374         int i,j,k;375         sort(p,p+n);376         convex.n=n;377         for (i=0;i<min(n,2);i++)378         {379             convex.p[i]=p[i];380         }381         if (n<=2)return;382         int &top=convex.n;383         top=1;384         for (i=2;i<n;i++)385         {386             while (top&&convex.p[top].sub(p[i]).det(convex.p[top-1].sub(p[i]))<=0)387                 top--;388             convex.p[++top]=p[i];389         }390         int temp=top;391         convex.p[++top]=p[n-2];392         for (i=n-3;i>=0;i--)393         {394             while (top!=temp&&convex.p[top].sub(p[i]).det(convex.p[top-1].sub(p[i]))<=0)395                 top--;396             convex.p[++top]=p[i];397         }398     }399     //判断是否凸多边形400     bool isconvex()401     {402         bool s[3];403         memset(s,0,sizeof(s));404         int i,j,k;405         for (i=0;i<n;i++)406         {407             j=(i+1)%n;408             k=(j+1)%n;409             s[dblcmp(p[j].sub(p[i]).det(p[k].sub(p[i])))+1]=1;410             if (s[0]&&s[2])return 0;411         }412         return 1;413     }414     //点与多边形关系415     //0 外部416     //1 内部417     //2 边上418     //3 点上419     int relationpoint(point q)420     {421         int i,j;422         for (i=0;i<n;i++)423         {424             if (p[i]==q)return 3;425         }426         getline();427         for (i=0;i<n;i++)428         {429             if (l[i].pointonseg(q))return 2;430         }431         int cnt=0;432         for (i=0;i<n;i++)433         {434             j=(i+1)%n;435             int k=dblcmp(q.sub(p[j]).det(p[i].sub(p[j])));436             int u=dblcmp(p[i].y-q.y);437             int v=dblcmp(p[j].y-q.y);438             if (k>0&&u<0&&v>=0)cnt++;439             if (k<0&&v<0&&u>=0)cnt--;440         }441         return cnt!=0;442     }443     //线段与多边形关系444     //0 无任何交点445     //1 在多边形内长度为正446     //2 相交或与边平行447     int relationline(line u)448     {449         int i,j,k=0;450         getline();451         for (i=0;i<n;i++)452         {453             if (l[i].segcrossseg(u)==2)return 1;454             if (l[i].segcrossseg(u)==1)k=1;455         }456         if (!k)return 0;457         vector<point>vp;458         for (i=0;i<n;i++)459         {460             if (l[i].segcrossseg(u))461             {462                 if (l[i].parallel(u))463                 {464                     vp.pb(u.a);465                     vp.pb(u.b);466                     vp.pb(l[i].a);467                     vp.pb(l[i].b);468                     continue;469                 }470                 vp.pb(l[i].crosspoint(u));471             }472         }473         sort(vp.begin(),vp.end());474         int sz=vp.size();475         for (i=0;i<sz-1;i++)476         {477             point mid=vp[i].add(vp[i+1]).div(2);478             if (relationpoint(mid)==1)return 1;479         }480         return 2;481     }482     //直线u切割凸多边形左侧483     //注意直线方向484     void convexcut(line u,polygon &po)485     {486         int i,j,k;487         int &top=po.n;488         top=0;489         for (i=0;i<n;i++)490         {491             int d1=dblcmp(p[i].sub(u.a).det(u.b.sub(u.a)));492             int d2=dblcmp(p[(i+1)%n].sub(u.a).det(u.b.sub(u.a)));493             if (d1>=0)po.p[top++]=p[i];494             if (d1*d2<0)po.p[top++]=u.crosspoint(line(p[i],p[(i+1)%n]));495         }496     }497     //取得周长498     double getcircumference()499     {500         double sum=0;501         int i;502         for (i=0;i<n;i++)503         {504             sum+=p[i].distance(p[(i+1)%n]);505         }506         return sum;507     }508     //取得面积509     double getarea()510     {511         double sum=0;512         int i;513         for (i=0;i<n;i++)514         {515             sum+=p[i].det(p[(i+1)%n]);516         }517         return fabs(sum)/2;518     }519     bool getdir()//1代表逆时针 0代表顺时针520     {521         double sum=0;522         int i;523         for (i=0;i<n;i++)524         {525             sum+=p[i].det(p[(i+1)%n]);526         }527         if (dblcmp(sum)>0)return 1;528         return 0;529     }530     //取得重心531     point getbarycentre()532     {533         point ret(0,0);534         double area=0;535         int i;536         for (i=1;i<n-1;i++)537         {538             double tmp=p[i].sub(p[0]).det(p[i+1].sub(p[0]));539             if (dblcmp(tmp)==0)continue;540             area+=tmp;541             ret.x+=(p[0].x+p[i].x+p[i+1].x)/3*tmp;542             ret.y+=(p[0].y+p[i].y+p[i+1].y)/3*tmp;543         }544         if (dblcmp(area))ret=ret.div(area);545         return ret;546     }547     //点在凸多边形内部的判定548     int pointinpolygon(point q)549     {550         if (getdir())reverse(p,p+n);551         if (dblcmp(q.sub(p[0]).det(p[n-1].sub(p[0])))==0)552         {553             if (line(p[n-1],p[0]).pointonseg(q))return n-1;554             return -1;555         }556         int low=1,high=n-2,mid;557         while (low<=high)558         {559             mid=(low+high)>>1;560             if (dblcmp(q.sub(p[0]).det(p[mid].sub(p[0])))>=0&&dblcmp(q.sub(p[0]).det(p[mid+1].sub(p[0])))<0)561             {562                 polygon c;563                 c.p[0]=p[mid];564                 c.p[1]=p[mid+1];565                 c.p[2]=p[0];566                 c.n=3;567                 if (c.relationpoint(q))return mid;568                 return -1;569             }570             if (dblcmp(q.sub(p[0]).det(p[mid].sub(p[0])))>0)571             {572                 low=mid+1;573             }574             else575             {576                 high=mid-1;577             }578         }579         return -1;580     }581 };582 583 struct polygon P[100],R[100];       //P:continent    R:convex of the continent584 struct point key[100];              //key point585 int T,C,N,M;586 587 588 int main()589 {590     freopen("in.txt","r",stdin);591 592     cin>>T;593     while (T--)594     {595         cin>>C>>N;596         for (int i=1;i<=N;i++)597             key[i].input();598         for (int i=1;i<=C;i++)599         {600             cin>>M;601             P[i].n=M;602             P[i].input();603             P[i].getline();604             for (int j=1;j<=N;j++)605             {606                 if (P[i].relationpoint(key[j])==0)  //outside607                     key[j].dis=0;608                 else609                     key[j].dis=1;610             }611         }612         double mmx=0,dist;613         struct line maxLN;614         for (int i=1;i<N;i++)615         {616             struct line LN;617             LN.a=key[i];    LN.b=key[i+1];618             int tn=0;619             double tp[100];620             for (int j=1;j<=C;j++)      //continent j621             {622                 for (int k=0;k<P[j].n;k++)  //line k in continent j623                 {624                     line TL=P[j].l[k];625                     if (LN.segcrossseg(TL)!=0)626                     {627                         point tm=LN.crosspoint(TL); //crosspoint of continent && flight route628                         tp[tn]=key[i].distance(tm);629                         tn++;630                     }631                 }632             }633             for (int ii=0;ii<tn;ii++)  printf("%.6f ",tp[ii]);  printf("\n");634             sort(tp,tp+tn,cmp);635             for (int ii=0;ii<tn;ii++)  printf("%.6f ",tp[ii]);  printf("\n");636             if (key[i].dis==0)  //outside637             {638                 for (int j=0;j<tn;j=j+2)639                 {640                     double TM;641                     if (j==0)   TM=tp[j];   else TM=tp[j]-tp[j-1];642                     if (TM>mmx) 643                     {644                         maxLN=LN;645                         mmx=TM;646                         if (j==0) dist=mmx/2; else dist=tp[j-1]+mmx/2;647                     }648                 }649             }650             else    //inside651             {652                 for (int j=1;j<tn;j=j+2)653                 {654                     double TM;655                     TM=tp[j]-tp[j-1];656                     if (TM>mmx) 657                     {658                         maxLN=LN;659                         mmx=TM;660                         dist=tp[j-1]+mmx/2;661                     }662                 }663             }664         }665         double dx=maxLN.a.distance(maxLN.b);    dx=dist/dx;666         point A=maxLN.a,B=maxLN.b;667         point Ans=(A.x+(B.x-A.x)*dx,A.y+(B.y-A.y)*dy);668         669                 670         printf("%.6f\n",mmx/2);671     }672     return 0;673 }