[SHOI 2008] 安全的航线

题目大意

航线用一段有 nn 个点的折线表示,cc 块陆地用不相交的多边形表示,定义「孤地点」为距离最近的陆地最远的地方,求孤地距离。

2n202 \leqslant n \leqslant 20

1c201 \leqslant c \leqslant 20

x,  y10,000|x|, \; |y| \leqslant 10,000

题目链接

【SHOI 2008】安全的航线 - Luogu 4286

题解

%%%%% 莫涛神犇:莫涛《迭代思想的应用》

%%%%% ydc 神犇:BZOJ 1020 | ydc的博客

把折线的每个线段放入队列,用 nn 个点更新一波答案。

每取出一条线段,记其两个端点到陆地的最近点为 p1p_1p2p_2,二分找到线段上的点 pp 使得 dist(p,p1)=dist(p,p2)dist(p, p _1) = dist(p, p_2) ,记为 rr ,这是当前线段能更新出的最大答案(而且可能去取不到),若有 ransr \leqslant ans 则直接删除该线段,否则从 pp 处切断线段并放入队列。反复以上操作直至队列为空。

一些细节需要注意,比如要写成 r <= ans + 0.05 就不会无法结束算法。

自己的方法名好长。。。( Java 的既视感?)

代码

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <cstdio>
#include <cmath>
#include <cfloat>
#include <queue>
#include <algorithm>
const int MAXN = 20;
const int MAXC = 20;
const int MAXM = 30;
const double EPS = 1e-5;
int dcmp(double x) {
if (fabs(x) <= EPS) return 0;
if (x > EPS) return 1;
return -1;
}
int c, n;
double ans;
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
double length() {
return sqrt(dot(*this, *this));
}
Point getPerpendicular() {
return Point(-y, x);
}
friend bool operator==(const Point &a, const Point &b) {
return !dcmp(a.x - b.x) && !dcmp(a.y - b.y);
}
friend Point operator+(const Point &a, const Point &b) {
return Point(a.x + b.x, a.y + b.y);
}
friend Point operator-(const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
}
friend Point operator*(const Point &p, const double a) {
return Point(p.x * a, p.y * a);
}
friend Point operator/(const Point &p, const double a) {
return Point(p.x / a, p.y / a);
}
friend double cross(const Point &a, const Point &b) {
return a.x * b.y - a.y * b.x;
}
friend double dot(const Point &a, const Point &b) {
return a.x * b.x + a.y * b.y;
}
friend double dist(const Point &a, const Point &b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
} flight[MAXN];
struct Node {
Point p;
double dist;
Node() {}
Node(const Point &p, double dist) : p(p), dist(dist) {}
};
struct Line {
Point p, v;
Line(const Point &p, const Point &v) : p(p), v(v) {}
friend Point getLineIntersection(const Line &a, const Line &b) {
Point u = a.p - b.p;
double t = cross(b.v, u) / cross(a.v, b.v);
return a.p + a.v * t;
}
};
struct Segment {
Point s, t;
Segment(const Point &s, const Point &t) : s(s), t(t) {}
friend Node getDistanceToSegment(const Point &p, const Segment &seg) {
if (seg.s == seg.t) return Node(seg.s, dist(p, seg.s));
Point vSeg = seg.t - seg.s, vs = p - seg.s, vt = p - seg.t;
if (dcmp(dot(vSeg, vs)) <= 0) return Node(seg.s, vs.length());
if (dcmp(dot(vSeg, vt)) >= 0) return Node(seg.t, vt.length());
Point v = vSeg.getPerpendicular();
Point inter = getLineIntersection(Line(p, v), Line(seg.s, vSeg));
return Node(inter, dist(p, inter));
}
friend bool isPointOnSegment(const Point &p, const Segment &seg) {
return dcmp(cross(seg.s - p, seg.t - p)) == 0 && dcmp(dot(seg.s - p, seg.t - p)) <= 0;
}
};
struct Polygen {
int size;
Point P[MAXM];
bool hasCovered(const Point &p) {
int windingNum = 0;
for (int i = 0; i < size; i++) {
if (isPointOnSegment(p, Segment(P[i], P[(i + 1) % size]))) return true;
int k = dcmp(cross(P[(i + 1) % size] - P[i], p - P[i]));
int d1 = dcmp(P[i].y - p.y);
int d2 = dcmp(P[(i + 1) % size].y - p.y);
if (k > 0 && d1 <= 0 && d2 > 0) windingNum++;
if (k < 0 && d2 <= 0 && d1 > 0) windingNum--;
}
return windingNum;
}
Point &operator[](int i) {
return P[i];
}
const Point operator[](int i) const {
return P[i];
}
} Poly[MAXC];
bool isPointInPolygens(const Point &p) {
for (int i = 0; i < c; i++) if (Poly[i].hasCovered(p)) return true;
return false;
}
Node getNode(const Point &p) {
if (isPointInPolygens(p)) return Node(p, 0);
Node res;
res.dist = DBL_MAX;
for (int i = 0; i < c; i++) for (int j = 0; j < Poly[i].size; j++) {
Node temp = getDistanceToSegment(p, Segment(Poly[i][j], Poly[i][(j + 1) % Poly[i].size]));
if (dcmp(res.dist - temp.dist) > 0) res = temp;
}
ans = std::max(ans, res.dist);
return res;
}
void search() {
std::queue<Segment> q;
getNode(flight[0]);
for (int i = 1; i < n; i++)
q.push(Segment(flight[i - 1], flight[i])), getNode(flight[i]);
while (!q.empty()) {
Segment u = q.front();
q.pop();
Point p1 = getNode(u.s).p, p2 = getNode(u.t).p;
Point l = u.s, r = u.t;
while (dcmp(dist(l, r)) > 0) {
Point mid = l + (r - l) / 2;
if (dist(p1, mid) < dist(p2, mid)) l = mid;
else r = mid;
}
double currLim = std::max(dist(p1, l), dist(p2, l));
getNode(l);
if (currLim > ans + 0.002) q.push(Segment(u.s, l)), q.push(Segment(l, u.t));
}
}
int main() {
scanf("%d %d", &c, &n);
for (int i = 0; i < n; i++) scanf("%lf %lf", &flight[i].x, &flight[i].y);
for (int i = 0; i < c; i++) {
scanf("%d", &Poly[i].size);
for (int j = 0; j < Poly[i].size; j++) scanf("%lf %lf", &Poly[i][j].x, &Poly[i][j].y);
}
search();
printf("%.2lf\n", ans);
return 0;
}