对于两只狗在经过拐点之前，他们的运动可以简化为一只狗不动，另一只狗以他们的相对速度运动；
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #define maxn 66 5 #define eps 1e-6 6 using namespace std; 7 8 struct node 9 { 10 double x,y; 11 node(double x=0,double y=0):x(x),y(y){ } 12 }; 13 node operator-(node u,node v){return node(u.x-v.x,u.y-v.y);} 14 node operator+(node u,node v){return node(u.x+v.x,u.y+v.y);} 15 node operator*(node u,double v){return node(u.x*v,u.y*v);} 16 node operator/(node u,double v){return node(u.x/v,u.y/v);} 17 int dcmp(double x) 18 { 19 if(fabs(x)<eps)return 0; 20 else return x<0?-1:1; 21 } 22 bool operator==(const node& a,const node& b) 23 { 24 return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0; 25 } 26 double dot(node a,node b){return a.x*b.x+a.y*b.y;} 27 double length(node a){return sqrt(dot(a,a));} 28 double cross(node a,node b){return a.x*b.y-a.y*b.x;} 29 double dis(const node& p,const node& a,const node& b) 30 { 31 if(a==b)return length(p-a); 32 node v1=b-a,v2=p-a,v3=p-b; 33 if(dcmp(dot(v1,v2))<0)return length(v2); 34 else if(dcmp(dot(v1,v3))>0)return length(v3); 35 else return fabs(cross(v1,v2))/length(v1); 36 } 37 int t,a,b; 38 double ma,mi; 39 node p[maxn],q[maxn]; 40 void update(const node& p,const node& a,const node& b) 41 { 42 mi=min(mi,dis(p,a,b)); 43 ma=max(ma,length(p-a)); 44 ma=max(ma,length(p-b)); 45 } 46 47 int main() 48 { 49 int ca=1; 50 scanf("%d",&t); 51 while(t--) 52 { 53 scanf("%d%d",&a,&b); 54 for(int i=0;i<a;i++)scanf("%lf %lf",&p[i].x,&p[i].y); 55 for(int i=0;i<b;i++)scanf("%lf %lf",&q[i].x,&q[i].y); 56 double lena=0,lenb=0; 57 for(int i=0;i<a-1;i++)lena+=length(p[i+1]-p[i]); 58 for(int i=0;i<b-1;i++)lenb+=length(q[i+1]-q[i]); 59 int sa=0,sb=0; 60 node pa=p[0],pb=q[0]; 61 mi=1e9,ma=-1e9; 62 while(sa<a-1&&sb<b-1) 63 { 64 double la=length(p[sa+1]-pa); 65 double lb=length(q[sb+1]-pb); 66 double t=min(la/lena,lb/lenb); 67 node va=(p[sa+1]-pa)/la*t*lena; 68 node vb=(q[sb+1]-pb)/lb*t*lenb; 69 update(pa,pb,pb+vb-va); 70 pa=pa+va; 71 pb=pb+vb; 72 if(pa==p[sa+1])sa++; 73 if(pb==q[sb+1])sb++; 74 } 75 printf("Case %d: %.0lf ",ca++,ma-mi); 76 } 77 return 0; 78 }