题目地址：https://vjudge.net/problem/UVA-11796
想法：对于A和B一起的每一线段，它们之间差的距离肯定要么是增函数，要么是减函数，所以答案只存在A处于莫个端点或B处于某个端点的时候
所以 剩下的目标就是如何枚举每一线段，然后更新
其中我还弄错了一个地方，我以为取答案的两个点肯定是在端点上，然而 不一定在端点上，那么在一起运动的时候，难得就是它们速度不一样，一个点在运动，另一个点也在，算两点的距离无从下手。看了刘汝佳的发现，用相对运动求解就好了，假设a禁止，那么b的运动向量Vb就是-Va，b点从b运动到b-Va
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <complex>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)/*Point模板部分*/
struct Point{double x,y;Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
//向量+向量=向量，点+向量=点
Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }
//点-点=向量
Vector operator - (Vector A, Vector B) { return Vector(A.x-B.x, A.y-B.y); }
//向量*数=向量
Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }
//向量/数=向量
Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }bool operator < (const Point& a, const Point& b) {return a.x < b.x || (a.x == b.x && a.y < b.y);
}//比较
const double eps = 1e-10;
int dcmp(double x){if(fabs(x) < eps) return 0;else return x < 0 ? -1: 1;
}bool operator == (const Point& a,const Point& b) {return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}//基本计算
double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
double Length(Vector A) { return sqrt(Dot(A,A)); }
double Angle(Vector A, Vector B) { return acos(Dot(A, B))/Length(A)/Length(B); }
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } //叉积
double Area2(Point A, Point B, Point C) { return Cross(B-A,C-A); } //有向面积//A向量逆时针旋转α rad
//x'=xcosα-ysinα;
//y'=xsinα+ycosα;
Vector Rotate(Vector A, double rad){return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}//A的单位法线,也就是逆时针90°，长度变为1，注意A要非零向量
Vector Normal(Vector A){ double L=Length(A);return Vector(-A.y/L,A.x/L);
}
/*Point模板部分*//*Segment模板部分*/
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w){ //两直线的交点，前提是Cross(v,w)!=0Vector u=P-Q;double t=Cross(w,u)/Cross(v,w);return P+v*t;
}
double DistanceToLine(Point P, Point A, Point B){ //P到直线A-B距离Vector v1=B-A, v2=P-A;return fabs(Cross(v1,v2) / Length(v1));
}
double DistanceToSegment(Point P, Point A, Point B){ //P到线段A-B距离if(A==B) return Length(P-A);Vector 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 fabs(Cross(v1,v2)) / Length(v1);
}
Point GetLineProjection(Point P, Point A, Point B){ //求P到直线A-B垂点Vector v=B-A;return A+v*(Dot(v,P-A)) / Dot(v,v);
}
bool SegmentProPerIntersection(Point a1, Point a2, Point b1,Point b2){ //两线是否规范相交double c1=Cross(a2-a1,b1-a1), c2=Cross(a2-a1,b2-a1),c3=Cross(b2-b1,a1-b1), c4=Cross(b2-b1,a2-b1);return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
}
bool OnSegment(Point p, Point a1, Point a2){ //p点是否在a1,a2线段上(不在a1,a2点上)return dcmp(Cross(a1-p,a2-p))==0 && dcmp(Dot(a1-p,a2-p)) < 0;
}
Vector Unit(Vector p){return p/Length(p);
}
Point ReadPoint(){double a,b;scanf("%lf%lf",&a,&b);return Point(a,b);
}
/*Segment模板部分*/const int maxn=50+5;
Point a[maxn],b[maxn];
double Min,Max;
void Update(Point P,Point A,Point B){Min=min(Min,DistanceToSegment(P,A,B));Max=max(Max,Length(P-A));Max=max(Max,Length(P-B));
}
int main(int argc, char const *argv[])
{// freopen("input.in","r",stdin);int T,kase=0; scanf("%d",&T);while(T--){int A,B;scanf("%d %d",&A,&B);REP(i,1,A) a[i]=ReadPoint();REP(i,1,B) b[i]=ReadPoint();double LenA=0,LenB=0;REP(i,1,A-1) LenA+=Length(a[i+1]-a[i]);REP(i,1,B-1) LenB+=Length(b[i+1]-b[i]);Point Pa=a[1],Pb=b[1];int Sa=1,Sb=1;Max=Min=Length(a[1]-b[1]);while(Sa<A&&Sb<B){double La=Length(a[Sa+1]-Pa);double Lb=Length(b[Sb+1]-Pb);double T=min(La/LenA,Lb/LenB); //A的速度为LenA，B的速度为LenBVector Va=Unit(a[Sa+1]-Pa)*T*LenA;Vector Vb=Unit(b[Sb+1]-Pb)*T*LenB;Update(Pa,Pb,Pb+Vb-Va); //把a看成禁止，那么对b来说相对走了(-Va)再加上Vb，就是相对走的距离Pa=Pa+Va;Pb=Pb+Vb;if(Pa==a[Sa+1]) Sa++;if(Pb==b[Sb+1]) Sb++;}printf("Case %d: %.0lf\n", ++kase,Max-Min);}return 0;
}