1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 50010 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 struct point 18 { 19     double x,y; 20     int id; 21     point(double x=0,double y = 0):x(x),y(y) {} 22 } p[N],q[N]; 23 struct node 24 { 25     int u,v; 26     double w; 27 } ed[N<<4]; 28 int fa[N],g; 29 double t1[N],t2[N]; 30 point a,b,c,d; 31 typedef point pointt; 32 point operator -(point a,point b) 33 { 34     return point(a.x-b.x,a.y-b.y); 35 } 36 int dcmp(double x) 37 { 38     if(fabs(x)<eps) return 0; 39     return x<0?-1:1; 40 } 41  42 double dis(point a) 43 { 44     return sqrt(a.x*a.x+a.y*a.y); 45 } 46 bool cmmp(node ta,node tb) 47 { 48     return ta.w<tb.w; 49 } 50 int findx(int x) 51 { 52     if(x!=fa[x]) 53         fa[x] = findx(fa[x]); 54     return fa[x]; 55 } 56 void add(point ta,point tb) 57 { 58     ed[++g].u = ta.id; 59     ed[g].v = tb.id; 60     ed[g].w = dis(ta-tb); 61 } 62 int main() 63 { 64     // freopen("data.in","r",stdin); 65     // freopen("data.out","w",stdout); 66     int t,i,n,m; 67     int kk = 0; 68     cin>>t; 69     while(t--) 70     { 71         scanf("%d%d",&n,&m); 72         scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y); 73         for(i = 0; i <= n+m ; i++) 74             fa[i] = i; 75         for(i = 0; i < n; i++) 76         { 77             scanf("%lf",&t1[i]); 78  79             // cout<<p[i].x<<" "<<p[i].y<<endl; 80         } 81         for(i = 0; i< m; i++) 82         { 83             scanf("%lf",&t2[i]); 84  85         } 86         sort(t1,t1+n); 87         sort(t2,t2+m); 88         int h=0; 89         for(i=0;i<n;i++) 90             if(i==n-1||t1[i]!=t1[i+1]) 91                 t1[h++]=t1[i]; 92         n=h; 93         h=0; 94         for(i=0;i<m;i++) 95             if(i==m-1||t2[i]!=t2[i+1]) 96                 t2[h++]=t2[i]; 97         m=h; 98         for(i = 0; i < n;i++) 99         {100              p[i] = point(a.x*t1[i]+b.x*(1-t1[i]),a.y*t1[i]+b.y*(1-t1[i]));101              p[i].id = i+1;102         }103         for(i = 0 ; i < m ; i++)104         {105             q[i] = point(c.x*t2[i]+d.x*(1-t2[i]),c.y*t2[i]+d.y*(1-t2[i]));106             q[i].id = i+n+1;107         }108         g = 0;109         double sum1 = 0,sum2 = 0;110         for(i = 0 ; i < n-1 ; i++)111         {112             add(p[i],p[i+1]);113             sum1+=dis(p[i]-p[i+1]);114         }115         for(i = 0 ; i < m-1 ; i++)116         {117             add(q[i],q[i+1]);118             sum2+=dis(q[i]-q[i+1]);119         }120         if(n==0||m==0)121         {122 123             printf("Case #%d: %.3lf\n",++kk,sum1+sum2);124             continue;125         }126         for(i = 0; i < n; i++)127         {128 //            point pp ;129 //            if(dcmp(c.x-d.x)==0)130 //            pp = point(c.x,p[i].y);131 //            else132 //            pp = dispoint(c,d,p[i]);133 //            if(dcmp(pp.x-min(c.x,d.x))<=0||dcmp(pp.x-max(c.x,d.x))>=0)134 //            {135 //                add(i,n+1);136 //                if(n+2<n+m)137 //                add(i,n+2);138 //                if(n+m-1>n+1)139 //                add(i,n+m-1);140 //                add(i,n+m);141 //                continue;142 //            }143 //            int k = find(n+1,n+m,c,dis(pp-c));144             // cout<<p[k].id<<" "<<pp.x<<" "<<pp.y<<endl;145 //            add(i,k);146 //            if(k!=n+1)147 //            add(i,k-1);148 //            if(k!=n+m)149 //            add(i,k+1);150             int l, r;151             l = 0;152             r = m-1;153             while (r - l > 1)154             {155                 int mid1 = (r + l) >> 1;156                 int mid2 = (mid1 + r) >> 1;157                 if (dis(p[i]-q[mid1]) > dis(p[i]-q[mid2]))158                     l = mid1;159                 else160                     r = mid2;161             }162 //            int k = find(1,n,a,dis(pp-a));163             add(p[i],q[l]);164             add(p[i],q[r]);165             if(l-1>=0)166                 add(p[i],q[l-1]);167             if(r+1<=m-1)168                 add(p[i],q[r+1]);169         }170         sort(ed+1,ed+g+1,cmmp);171         int num = 0;172         double sum = 0;173         for(i = 1; i <= g; i++)174         {175             int tx = findx(ed[i].u);176             int ty = findx(ed[i].v);177             if(tx!=ty)178             {179                 fa[tx] = ty;180                 num++;181                 sum+=ed[i].w;182             }183         }184         printf("Case #%d: %.3f\n",++kk,sum);185     }186     return 0;187 }