题意 两条狗啊，同时跑，，同时结束，各自跑各自的道路，问跑的过程中，他们最大距离和最小距离的差；
方法 恶心一点就是，最大最小距离的求解方法，假设两只狗都只有一条线段要跑，则可以判定在端点处有最大值，最小值的求解方法就是，把一条狗的奔跑方向分解成另一个狗的奔跑方向 + 另外一个向量，这样这条狗相对于另外一条狗处于相对静止；只要求点到线段的最小距离便是； 如果有两段以上的线段；考虑第一条线段；肯定会有一条狗先跑完第一段，另外一条狗没有跑完第一段，根据比例关系我们可以知道那条没有跑完的狗跑到那里了，因此可以得到那条没有跑完的狗的终点坐标；然后这条没有跑完的狗的下一条线段，就是这个终点到，，，，当前自己的终点；就这样一直跑下去
#include<iostream> #include<stdio.h> #include<cstring> #include<algorithm> #include<cmath> #include<functional> #define eps 1e-9 #include<vector> using namespace std; const double PI = acos(-1.0); int dcmp( double x ){ if( abs(x) < eps ) return 0;else return x < 0?-1:1; } struct point{ double x,y; point( double x = 0,double y = 0 ):x(x),y(y){} }node[112]; typedef point Vector; struct segment{ point a,b; segment(){} segment(point _a,point _b){a=_a,b=_b;} }; struct circle{ point c; double r; circle(){} circle(point _c, double _r):c(_c),r(_r) {} point PPP(double a)const{return point(c.x+cos(a)*r,c.y+sin(a)*r);} }; struct line{ point p,v; double ang; line() {} line( const point &_p, const point &_v):p(_p),v(_v){ang = atan2(v.y, v.x);} inline bool operator < (const line &L)const{return ang < L.ang;} }; point operator + (point a,point b){return point( a.x + b.x,a.y + b.y );} point operator - (point a,point b){return point( a.x - b.x,a.y - b.y );} point operator * (point a,double b){return point( a.x*b,a.y*b );} point operator / (point a,double b){ return point( a.x/b,a.y/b );} bool operator < (const point &a, const point &b ){return a.x < b.x || (a.x == b.x && a.y < b.y );} bool operator == (const point &a, const point &b ){return (dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0 );} bool operator != (const point &a,const point &b ){return a == b?false:true;} double Dot( point a,point b ){return a.x*b.x + a.y*b.y;} // 点到点的距离； double Length( point a ){return sqrt( Dot( a,a ) );} // 向量长度 double Angle( point a,point b ){ return acos( Dot(a,b)/Length(a)/Length(b) );} // 两个向量的角度 double D_T_D(const double ° ){ return deg/180*PI; } // 向量旋转 rad 度数 point Rotate( point a, double rad ){ return point( a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad) ); } // 向量的 法线向量 的单位向量 point Normal( point a ){ double L = Length(a); return point(-a.y/L,a.x/L); } // 叉积计算 double Cross( point a,point b ){ return a.x*b.y - a.y*b.x; } // 获取 两个向量叉积 double get_Mix( point a,point b,point pot ){ a.x = a.x - pot.x; a.y = a.y - pot.y; b.x = b.x - pot.x; b.y = b.y - pot.y; return Cross( a,b ); } // 直线相交求交点； point get_line_inter( point p,point v, point q,point w ){ point u = p - q; double t = Cross(w,u)/Cross(v,w); return p+v*t; } // p点到直线 的距离 double dis_p_line( point p,point a,point b ) { point v1 = b-a, v2 = p-a; return abs( Cross(v1,v2)/Length(v1) ); } //点在直线上的投影 inline point GetLineProjection(const point &p,const point &a,const point &b){ point v=b-a; return a+v*(Dot(v,p-a)/Dot(v,v)); } // 点到线段的距离 double dis_p_segm( point p,point a,point b ){ if( a == b )return Length( p-a ); point v1 = b-a,v2 = p-a,v3 = p-b; if( dcmp(Dot(v1,v2)) < 0 )return Length(v2); else if( dcmp(Dot( v1,v3)) > 0 )return Length(v3); else return abs(Cross( v1,v2 ))/Length(v1); } //海伦公式 三条边 double Heron(double a,double b,double c){ double p=(a+b+c)/2; return sqrt(p*(p-a)*(p-b)*(p-c)); } // 多边形面积 从p[0] 开始，p[n] 结束 double ploy_area( point *p,int n ){ double area = 0; for( int i = 1; i < n-1; i++ ) area += Cross( p[i]-p[0],p[i+1]-p[0] ); return area/2.0; } // 线段相交判断 先必须去掉不相交的状态；再判断方向 bool get_set( point a,point b,point c,point d ){ if( min( a.x,b.x ) <= max( c.x,d.x ) && min( a.y,b.y ) <= max( c.y,d.y ) && min( c.x,d.x ) <= max( a.x,b.x ) && min( c.y,d.y ) <= max( a.y,b.y ) && Cross( c-b,a-b )*Cross( d-b,a-b ) <= 0 && Cross( a-d,c-d )*Cross( b-d,c-d ) <= 0 ) return true; return false; } // 线段 直线 平行判断只需要对应向量平行； bool get_pall( point a,point b,point c,point d ){ if( Cross( a-b,c-d ) == 0 )return true; return false; } // 直线 重合判断 只需要 一条直线的两点都在直线方向 bool get_doub( point a,point b,point c,point d ){ if( Cross( d-b,a-b ) == 0 && Cross( c-b,a-b ) == 0 )return 1; return 0; } // 获取 线段 交点；依据 叉积判断 point get_pot( point a,point b,point c,point d ){ point temp; temp.x = ( c.x*Cross(b-a,d-a) - d.x*Cross(b-a,c-a) )/( Cross(b-a,d-a) - Cross(b-a,c-a) ); temp.y = ( c.y*Cross(b-a,d-a) - d.y*Cross(b-a,c-a) )/( Cross(b-a,d-a) - Cross(b-a,c-a) ); return temp; } //获取直线的交点 同时也可以是线段的交点； point get_ppp( point a,point b,point c,point d ){ double a0 = a.y - b.y; double b0 = b.x - a.x; double c0 = a.x*b.y - b.x*a.y; double a1 = c.y - d.y; double b1 = d.x - c.x; double c1 = c.x*d.y - d.x*c.y; double D = a0*b1 - a1*b0; point temp; temp.x = ( b0*c1 - b1*c0 )/D; temp.y = ( a1*c0 - a0*c1 )/D; return temp; } //点pot 是否 在线段 ab 上 只需 叉积等于0 点积等于0 bool online( point a,point b,point pot ){ if( Cross( a - pot,b - pot ) == 0 && Dot( a - pot,b - pot ) <= 0 )return 1; return 0; } int top,res[1123456]; // 凸包 ( 起点 0 ) ( n 个点 ) 自己写的，，需要改进 改进； void GRA( int n ) { sort( node,node+n ); // 先排序 top = 1; res[0] = 0; res[1] = 1;// 从第0位开始放；前两位不管 for( int i = 2; i <= n; i++ ){ while( top && get_Mix( node[i],node[res[top]],node[res[top-1]] ) > 0 )top--; res[++top] = i; } int k = top; for( int i = n-2; i >= 0; i-- ){ while( top > k && get_Mix( node[i],node[res[top]],node[res[top-1]] ) > 0 )top--; res[++top] = i; } top--; // 会添加进去最后一个点 } //求两圆相交 int C_T_C( circle c1,circle c2,point &p1,point &p2 ){ double d = Length( c1.c- c2.c ); if( dcmp( d ) == 0 ) { if( dcmp( c1.r-c2.r ) == 0 ) return -1;//两圆重合 return 0; } if( dcmp( c1.r + c2.r - d ) < 0 ) return 0; if( dcmp( fabs( c1.r - c2.r ) - d ) > 0 ) return 0; double a = Angle( c2.c - c1.c,point( 1,0 ) ); double da = acos(( c1.r * c1.r + d * d - c2.r * c2.r )/( 2 * c1.r * d ) ); p1 = c1.PPP( a - da ); p2 = c1.PPP( a + da ); if( p1 == p2 ) return 1; return 2; } //圆与直线交点 返回交点个数 int C_T_L( line L,circle C,point &p1,point &p2){ double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y-C.c.y; double e = a*a + c*c, f = 2*(a*b+c*d), g = b*b + d*d -C.r*C.r; double delta = f*f - 4*e*g; if( dcmp(delta) < 0 ) return 0;//相离 if( dcmp(delta) == 0 ) {//相切 p1 = p1 = L.p + L.v*( -f/(2*e) ); return 1; }//相交 p1 = ( L.p + L.v * ( -f-sqrt(delta) )/( 2*e ) ); p2 = ( L.p + L.v * ( -f+sqrt(delta) )/( 2*e ) ); return 2; } //点与圆的切线； int get_P_C_inter( point p,circle c, point *v ) { point u = c.c - p; double dist = Length(u); if( dist < c.r )return 0; else if( dcmp( dist - c.r) == 0 ){ v[0] = Rotate( u,PI/2 ); return 1; }else { double ang = asin( c.r/dist ); v[0] = Rotate(u,-ang); v[1] = Rotate(u,+ang); return 2; } return -1; } point A[100],B[100]; int main( ) { int T,N,M,cas = 1;scanf("%d",&T); while( T-- ) { double sum1 = 0; double sum2 = 0; scanf("%d%d",&N,&M); for( int i = 1; i <= N; i++ ){ scanf("%lf%lf",&A[i].x,&A[i].y); if( i != 1 )sum1 += Length( A[i]-A[i-1] ); } for( int i = 1; i <= M; i++ ){ scanf("%lf%lf",&B[i].x,&B[i].y); if( i != 1 )sum2 += Length( B[i]-B[i-1] ); } double Bi = sum1/sum2; double Max = 0;double Min = (1<<30); int ans1 = 2; int ans2 = 2; point sta = A[1]; point end = A[2]; point u = B[1]; point v = B[2]; while( ans1 <= N && ans2 <= M ) { if( Length(end-sta)/Length(v-u) > Bi ) { point tp; tp = sta + (end-sta)*Length(v-u)*Bi/Length(end-sta); Max = max( Max,max( Length(tp-v),Length(sta-u) ) ); point temp; temp = sta + ( (tp - sta) - ( v - u ) ); Min = min( Min, dis_p_segm( u,sta,temp ) ); sta = tp; u = v; v = B[++ans2]; }else { point tp; tp = u + (v-u)*Length(end-sta)/Bi/Length(v-u); Max = max( Max,max( Length(end-tp),Length(sta-u) ) ); point temp; temp = sta + ( (end - sta) - ( tp - u ) ); Min = min( Min, dis_p_segm( u,sta,temp ) ); u = tp; sta = end; end = A[++ans1]; } } printf("Case %d: %.lf ",cas++,Max-Min); } return 0; }