首页 > 代码库 > UVa 11796 Dog Distance
UVa 11796 Dog Distance
题意：
有甲乙两条狗分别沿着一条折线奔跑，已知它们同时从各自的起点出发，同时到达各自的终点。求整个过程中两条狗的最大距离Max与最小距离Min的差值。
分析：
假设甲乙的路线都是一条线段的简单情况。运动是相对的，我们假定甲不动，乙相对甲的运动也是匀速直线运动。所以就将问题转化成了点到直线的最小和最大距离。
甲或乙每到达一个拐点所对应的时刻称作“关键点”，那么没两个关键点之间的运动都可看做上面分析的简单情况。我们只要及时更新甲乙的位置即可。
LenA和LenB分别是两条路线的总长，因为运动时间相同，不妨设二者的运动速度为LenA和LenB，这样总时间为1
1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 8 struct Point 9 {10 double x, y;11 Point(double x=0, double y=0) :x(x),y(y) {}12 };13 typedef Point Vector;14 Point read_point(void)15 {16 double x, y;17 scanf("%lf%lf", &x, &y);18 return Point(x, y);19 }20 const double EPS = 1e-8;21 Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }22 Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }23 Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }24 Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }25 bool operator < (const Point& a, const Point& b)26 { return a.x < b.x || (a.x == b.x && a.y < b.y); }27 int dcmp(double x)28 { if(fabs(x) < EPS) return 0; else return x < 0 ? -1 : 1; }29 bool operator == (const Point& a, const Point& b)30 { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; }31 double Dot(Vector A, Vector B)32 { return A.x*B.x + A.y*B.y; }33 double Length(Vector A) { return sqrt(Dot(A, A)); }34 35 double Cross(Vector A, Vector B)36 { return A.x*B.y - A.y*B.x; }37 double DistanceToSegment(Point P, Point A, Point B)38 {39 if(A == B) return Length(P - A);40 Vector v1 = B - A, v2 = P - A, v3 = P - B;41 if(dcmp(Dot(v1, v2)) < 0) return Length(v2);42 else if(dcmp(Dot(v1, v3)) > 0) return Length(v3);43 else return fabs(Cross(v1, v2)) / Length(v1);44 }45 const int maxn = 60;46 Point P[maxn], Q[maxn];47 double Min, Max;48 49 void update(Point P, Point A, Point B)50 {51 Min = min(Min, DistanceToSegment(P, A, B));52 Max = max(Max, Length(P-A));53 Max = max(Max, Length(P-B));54 }55 56 int main(void)57 {58 #ifdef LOCAL59 freopen("11796in.txt", "r", stdin);60 #endif61 62 int T, A, B;63 scanf("%d", &T);64 for(int kase = 1; kase <= T; ++kase)65 {66 int A, B;67 scanf("%d%d", &A, &B);68 for(int i = 0; i < A; ++i) P[i] = read_point();69 for(int i = 0; i < B; ++i) Q[i] = read_point();70 71 double LenA = 0.0, LenB = 0.0;72 for(int i = 0; i < A-1; ++i) LenA += Length(P[i+1] - P[i]);73 for(int i = 0; i < B-1; ++i) LenB += Length(Q[i+1] - Q[i]);74 75 int Sa = 0, Sb = 0; //甲乙当前端点的编号76 Point Pa = P[0], Pb = Q[0];77 Min = 1e9, Max = -1e9;78 while(Sa < A-1 && Sb < B-1)79 {80 double La = Length(P[Sa+1] - Pa); //甲乙分别到下一拐点的距离81 double Lb = Length(Q[Sb+1] - Pb);82 double T = min(La / LenA, Lb / LenB);83 Vector Va = (P[Sa+1] - Pa) / La * T * LenA;84 Vector Vb = (Q[Sb+1] - Pb) / Lb * T * LenB;85 update(Pa, Pb, Pb + Vb - Va);86 Pa = Pa + Va;87 Pb = Pb + Vb;88 if(Pa == P[Sa+1]) Sa++;89 if(Pb == Q[Sb+1]) Sb++;90 }91 92 printf("Case %d: %.0lf\n", kase, Max - Min);93 }94 return 0;95 }
UVa 11796 Dog Distance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。