解題區/解題區 - UVa

UVa 10961 - Chasing After Don Giovanni

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

A 要追 B，結果 B 偽裝成 C，B 告訴 A，B 將會怎麼走並且沿路指導 A 該怎麼走，然而真正的 C 也會在地圖中某一個地方開始移動。

如果 A、C 相遇，則會發現 B 是偽裝的，給予兩個人的路線，請問 B 是否能安全抵達目的地，如果再目的地被抓到也相當於安全抵達，因為他已經抵達目的地。

假設 A、C 的移動速度相同。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
2 3
5 2
3
5 4
3 4
3 6
4
4 3
4 5
5 5
5 6
2 2
4 2
3
6 2
6 3
3 3
3
2 4
5 4
5 6

Sample Output

1
2
3
No
Yes

Solution

這一題與 11796 - Dog Distance 很類似。找兩個路線的最接近距離。

  • 题目大意：
    两条狗匀速分别沿着折线跑，已知同时出发，同时到达，问你求相差最大的距离 与相差的最小的距离之间的差值。
  • 解题思路：
    如果两只狗都走1条线段的话，根据相对运动的理论，可以把其中一只狗看成静止不动，另一只狗相对运动，且线路为线段，那么立刻转化为点到线段的距离的问题。
http://blog.csdn.net/a1061747415/article/details/38682243

而這一題檢查最近距離是否為 0 即可。特別 case 終點碰到的情況，此外測資中兩個路線的距離長貌似相同，因為討論區的有幾組不同長的測資，雖然以下代碼沒有通過，但是還是 AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
// similar 11796 - Dog Distance
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)	return x < a.x;
        return y < a.y;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
typedef Pt Vector;
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
double distProjection(Pt as, Pt at, Pt s) {
    double a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double distToSeg(Pt sa, Pt sb, Pt a) {
    if(!(sa == sb) && between(sa, sb, a))
        return distProjection(sa, sb, a);
    return min(dist(sa, a), dist(sb, a));
}
int main() {
    int testcase, cases = 0, A, B;
    Pt DA[105], DB[105];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%lf %lf", &DB[0].x, &DB[0].y);
        scanf("%lf %lf", &DA[0].x, &DA[0].y);
        scanf("%d", &A);
        for(int i = 1; i <= A; i++)
            scanf("%lf %lf", &DA[i].x, &DA[i].y);
        scanf("%d", &B);
        for(int i = 1; i <= B; i++)
            scanf("%lf %lf", &DB[i].x, &DB[i].y);
        A++, B++;
        double speed_a = 1, speed_b = 1;
        
        int aIdx, bIdx;
        double sa, sb, run;
        Vector va, vb;
        Pt apos = DA[0], bpos = DB[0];
        aIdx = bIdx = 0;
        
        double mxDist = 0, mnDist = 1e+30;
        while(aIdx < A - 1 && bIdx < B - 1) {
            sa = dist(DA[aIdx+1], apos);
            sb = dist(DB[bIdx+1], bpos);
            run = min(sa/speed_a, sb/speed_b); // run time
            va = (DA[aIdx+1] - apos)/sa * run * speed_a;
            vb = (DB[bIdx+1] - bpos)/sb * run * speed_b;
            if (bpos + vb == DB[B - 1] && apos + va == DA[A - 1]) { // a route is safe even if the villagers meet Leporello at the destination.
                mnDist = min(mnDist, dist(bpos, apos));
                if (!(bpos == bpos+vb-va) && between(bpos, bpos+vb-va, apos) && !(apos == bpos+vb-va))
                    mnDist = min(mnDist, distProjection(bpos, bpos+vb-va, apos));
            } else
                mnDist = min(mnDist, distToSeg(bpos, bpos+vb-va, apos));
//			mxDist = max(mxDist, dist(apos, bpos));
//			mxDist = max(mxDist, dist(apos, bpos+vb-va));
            apos = apos + va;
            bpos = bpos + vb;
            if(apos == DA[aIdx+1])
                aIdx++;
            if(bpos == DB[bIdx+1])
                bIdx++;
        }
        if (cases++)	puts("");
        if (fabs(mnDist) < eps)
            puts("No");
        else
            puts("Yes");
    } 
    return 0;
}
/*
*/