题意：
见白书...
思路：
我们只要按照相对运动来处理就好了，不过这里一定要理解，相对运动是通过向量来解决的，如果单纯的依靠速度来决定他的走向的话，只有两条线段平行的时候才可以。然后就是模拟这个相对运动的过程，看谁先到达拐点然后处理。
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <algorithm> #include <string> #include <set> #include <functional> #include <numeric> #include <sstream> #include <stack> #include <map> #include <queue> #define CL(arr, val) memset(arr, val, sizeof(arr)) #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define ll long long #define L(x) (x) << 1 #define R(x) (x) << 1 | 1 #define MID(l, r) (l + r) >> 1 #define Min(x, y) (x) < (y) ? (x) : (y) #define Max(x, y) (x) < (y) ? (y) : (x) #define E(x) (1 << (x)) #define iabs(x) (x) < 0 ? -(x) : (x) #define OUT(x) printf("%I64d ", x) #define lowbit(x) (x)&(-x) #define keyTree (chd[chd[root][1]][0]) #define Read() freopen("din.txt", "r", stdin) #define Write() freopen("dout.txt", "w", stdout); #define M 100 #define N 307 using namespace std; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1};//懈芯芯斜胁小褋褉 const int inf = 0x7f7f7f7f; const int mod = 1000000007; const double eps = 1e-8; struct Point { double x,y; Point(double tx = 0,double ty = 0) : x(tx),y(ty){} }; typedef Point Vtor; //向量的加减乘除 Vtor operator + (Vtor A,Vtor B) { return Vtor(A.x + B.x,A.y + B.y); } Vtor operator - (Point A,Point B) { return Vtor(A.x - B.x,A.y - B.y); } Vtor operator * (Vtor A,double p) { return Vtor(A.x*p,A.y*p); } Vtor operator / (Vtor A,double p) { return Vtor(A.x/p,A.y/p); } bool operator < (Point A,Point B) { return A.x < B.x || (A.x == B.x && A.y < B.y);} int dcmp(double x){ if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } bool operator == (Point A,Point B) {return dcmp(A.x - B.x) == 0 && dcmp(A.y - B.y) == 0; } //向量的点积，长度，夹角 double Dot(Vtor A,Vtor B) { return A.x*B.x + A.y*B.y; } double Length(Vtor A) { return sqrt(Dot(A,A)); } double Angle(Vtor A,Vtor B) { return acos(Dot(A,B)/Length(A)/Length(B)); } //叉积，三角形面积 double Cross(Vtor A,Vtor B) { return A.x*B.y - A.y*B.x; } double Area2(Point A,Point B,Point C) { return Cross(B - A,C - A); } //向量的旋转,求向量的单位法线（即左转90度，然后长度归一） Vtor Rotate(Vtor A,double rad){ return Vtor(A.x*cos(rad) - A.y*sin(rad),A.x*sin(rad) + A.y*cos(rad)); } Vtor Normal(Vtor A) { double L = Length(A); return Vtor(-A.y/L, A.x/L); } //直线的交点 Point GetLineIntersection(Point P,Vtor v,Point Q,Vtor w) { Vtor u = P - Q; double t = Cross(w,u)/Cross(v,w); return P + v*t; } //点到直线的距离 double DistanceToLine(Point P,Point A,Point B) { Vtor v1 = B - A; return Cross(P,v1)/Length(v1); } //点到线段的距离 double DistanceToSegment(Point P,Point A,Point B) { if (A == B) return Length(P - A); Vtor 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) { Vtor 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) { return dcmp(Cross(a1 - P,a2 - P)) == 0 && dcmp(Dot(a1 - P,a2 - P)) < 0; } //多边形面积 double PolgonArea(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; } Point P[N],Q[N]; double Ma,Mi; void update(Point a,Point b,Point c) { Mi = min(Mi,DistanceToSegment(a,b,c)); Ma = max(Ma,max(Length(b - a),Length(c - a))); } int n,m; int main() { // Read(); int T; int cas = 1; scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); Ma = -inf, Mi = inf; for (int i = 0; i < n; ++i) scanf("%lf%lf",&P[i].x,&P[i].y); for (int i = 0; i < m; ++i) scanf("%lf%lf",&Q[i].x,&Q[i].y); //求出总路程，可以当做速度 double La = 0,Lb = 0; for (int i = 0; i < n - 1; ++i) La += Length(P[i + 1] - P[i]); for (int i = 0; i < m - 1; ++i) Lb += Length(Q[i + 1] - Q[i]); int sa = 1,sb = 1; Point pa = P[0],pb = Q[0]; while (sa < n && sb < m) { double L1 = Length(P[sa] - pa); double L2 = Length(Q[sb] - pb); double t = min(L1/La,L2/Lb);//求出到达下一个拐点的时间 //求出位移量，注意这里是位移量。 Vtor va = (P[sa] - pa)/L1*t*La; Vtor vb = (Q[sb] - pb)/L2*t*Lb; //更新距离 update(pa,pb,pb + vb - va); //更新数据 pa = pa + va; pb = pb + vb; if (pa == P[sa]) sa++; if (pb == Q[sb]) sb++; // printf("Sa = %d Sb = %d ",sa,sb); } printf("Case %d: %.0lf ",cas++,Ma - Mi); } return 0; }