题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=31962
【代码】
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 6 const double eps = 1e-8; 7 int dcmp(double x) { if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } 8 9 struct Point { 10 double x, y; 11 Point(double x=0, double y=0):x(x),y(y) { } 12 }; 13 14 typedef Point Vector; 15 16 Vector operator + (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y); } 17 Vector operator - (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y); } 18 Vector operator * (const Vector& A, double p) { return Vector(A.x*p, A.y*p); } 19 Vector operator / (const Vector& A, double p) { return Vector(A.x/p, A.y/p); } 20 21 bool operator < (const Point& a, const Point& b) { 22 return a.x < b.x || (a.x == b.x && a.y < b.y); 23 } 24 25 bool operator == (const Point& a, const Point &b) { 26 return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; 27 } 28 29 Point read_point() { 30 double x, y; 31 scanf("%lf%lf", &x, &y); 32 return Point(x, y); 33 }; 34 35 double Dot(const Vector& A, const Vector& B) { return A.x*B.x + A.y*B.y; } 36 double Length(const Vector& A) { return sqrt(Dot(A, A)); } 37 double Cross(const Vector& A, const Vector& B) { return A.x*B.y - A.y*B.x; } 38 39 double DistanceToSegment(const Point& P, const Point& A, const Point& B) { 40 if(A == B) return Length(P-A); 41 Vector v1 = B - A, v2 = P - A, v3 = P - B; 42 if(dcmp(Dot(v1, v2)) < 0) return Length(v2); 43 else if(dcmp(Dot(v1, v3)) > 0) return Length(v3); 44 else return fabs(Cross(v1, v2)) / Length(v1); 45 } 46 47 const int maxn = 60; 48 int T, A, B; 49 Point P[maxn], Q[maxn]; 50 double Min, Max; 51 52 void update(Point P, Point A, Point B) { 53 Min = min(Min, DistanceToSegment(P, A, B)); 54 Max = max(Max, Length(P-A)); 55 Max = max(Max, Length(P-B)); 56 } 57 58 int main() { 59 scanf("%d", &T); 60 for(int kase = 1; kase <= T; kase++) { 61 scanf("%d%d", &A, &B); 62 for(int i = 0; i < A; i++) P[i] = read_point(); 63 for(int i = 0; i < B; i++) Q[i] = read_point(); 64 65 double LenA = 0, LenB = 0; 66 for(int i = 0; i < A-1; i++) LenA += Length(P[i+1]-P[i]); 67 for(int i = 0; i < B-1; i++) LenB += Length(Q[i+1]-Q[i]); 68 69 int Sa = 0, Sb = 0; 70 Point Pa = P[0], Pb = Q[0]; 71 Min = 1e9, Max = -1e9; 72 while(Sa < A-1 && Sb < B-1) { 73 double La = Length(P[Sa+1] - Pa); 74 double Lb = Length(Q[Sb+1] - Pb); 75 double T = min(La/LenA, Lb/LenB); 76 Vector Va = (P[Sa+1] - Pa)/La*T*LenA; 77 Vector Vb = (Q[Sb+1] - Pb)/Lb*T*LenB; 78 update(Pa, Pb, Pb+Vb-Va); 79 Pa = Pa + Va; 80 Pb = Pb + Vb; 81 if(Pa == P[Sa+1]) Sa++; 82 if(Pb == Q[Sb+1]) Sb++; 83 } 84 printf("Case %d: %.0lf\n", kase, Max-Min); 85 } 86 return 0; 87 }