解題區/解題區 - UVa

UVa 12173 - White Water Rafting

contents

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

Problem

給滑水道兩邊緣座標，求最大半徑的圓可以再滑水道之間穿越。

Sample Input

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

Sample Output

1
2
2.50000000
0.70710678

Solution

求所有點到線段的最短距離，轉角的部分一定會符合其中一邊的最大半徑，全部取最小即可。

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
118
119
120
121
122
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
using namespace std;
#define eps 1e-6
struct Pt {
    int x, y;
    Pt(int a = 0, int 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;
    }
    Pt operator-(const Pt &a) const {
        Pt ret;
        ret.x = x - a.x;
        ret.y = y - a.y;
        return ret;
    }
};
enum LINE_TYPE {LINE, SEGMENT};
struct LINE2D {
    Pt s, e;
    LINE_TYPE type;
};
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;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
double distProjection(Pt as, Pt at, Pt s) {
    int 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 dist2Seg(Pt sa, Pt sb, Pt p) {
    double c = 1e+30;
    if(between(sa, sb, p))
        c = min(c, distProjection(sa, sb, p));
    else
        c = min(c, min(dist(sa, p), dist(sb, p)));
    return c;
}
int main() {
    int testcase;
    int n, m;
    Pt Di[128], Do[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d %d", &Di[i].x, &Di[i].y);
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
            scanf("%d %d", &Do[i].x, &Do[i].y);
        
        double ret = 1e+30;
        Di[n] = Di[0], Do[m] = Do[0];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ret = min(ret, dist2Seg(Di[i], Di[i+1], Do[j]));
                ret = min(ret, dist2Seg(Do[j], Do[j+1], Di[i]));
            }
        }
        printf("%.8lf\n", ret/2);
    }
    return 0;
}
/*
 2
 4
 -5 -5
 5 -5
 5 5
 -5 5
 4
 -10 -10
 -10 10
 10 10
 10 -10
 3
 0 0
 1 0
 1 1
 5
 3 -3
 3 3
 -4 2
 -1 -1
 -2 -2
 */