题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2896
大概思路:A和B运动,以A(Posa)为参考点,求出B的运动轨迹(Posb -> Posb + Vb-Va);
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> using namespace std; const int maxn = 60; const int maxe = 100000; const int INF = 0x3f3f3f; const double eps = 1e-8; const double PI = acos(-1.0); 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); } 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 Cross(const Vector& A, const Vector& B) { return A.x*B.y - A.y*B.x; } ///求点P到线段AB的距离,先看Q点在线段外还是内;利用点积就可以, double DistanceToSegment(Point P,Point A,Point 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 read_point(){ Point A; scanf("%lf %lf",&A.x,&A.y); return A; } 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() { ///freopen("E:\\acm\\input.txt","r",stdin); ///freopen("E:\\acm\\output.txt","w",stdout); int T,a,b; Point A[maxn],B[maxn]; cin>>T; for(int t=1;t<=T;t++){ cin>>a>>b; for(int i=1;i<=a;i++) A[i] = read_point(); for(int i=1;i<=b;i++) B[i] = read_point(); double lenA = 0,lenB = 0; for(int i=1;i<a;i++) lenA += Length(A[i+1]-A[i]); for(int i=1;i<b;i++) lenB += Length(B[i+1]-B[i]); //这儿也能写错;复制就是不好。 int Sa = 1, Sb = 1; Point Posa = A[1], Posb = B[1]; // 现在甲乙所在的位置; Min = 1e9, Max = -1e9; while(Sa < a && Sb < b){ double La = Length(A[Sa+1]-Posa); double Lb = Length(B[Sb+1]-Posb); double T = min(La/lenA,Lb/lenB); // 取合适的单位,可以让甲和乙的速度分别是LenA和LenB Vector Va = (A[Sa+1]-Posa)/La * T * lenA; //A在这次比较下的位移向量; Vector Vb = (B[Sb+1]-Posb)/Lb * T * lenB; update(Posa,Posb,Posb+Vb-Va); //Vb-Va是A在相对静止时,B的位移向量; Posa = Posa + Va; Posb = Posb + Vb; if(Posa == A[Sa+1]) Sa++; if(Posb == B[Sb+1]) Sb++; } printf("Case %d: %.0lf\n",t,Max-Min); } return 0; }