UVa 754 - Treasure Hunt

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
1
7
20 0 37 100
40 0 76 100
85 0 0 75
100 90 0 90
0 71 100 61
0 14 100 38
100 47 47 100
54.5 55.4

Sample Output

1
Number of doors = 2

Solution

網路上有人使用半平面交,不斷地從寶藏所在之處的凸包,每次拿凸包邊的中點,外偏一點再找半平面交,直到碰到外界。但外偏多少才能保證會在另一個密室?這外偏的想法當然不錯,但想到誤差可能,還是先挑戰別的想法。精神還是繞著 Bfs 走。

把之前的 Point Location 拿出來用,先用 Partition Slab Map 頂替,用 Trapezoidal Map 可能就 … 寫個半條命。得到可以支持 Point Location 的資料結構後,把 Dual graph 建造出來,就可以 Bfs 收工。

Partition Slab Map

Dual graph

夢月 (dreamoon) 提供更簡單實作的想法

n 只有 30,而且他的平面圗是很多直線構成的,對於每個區塊,我們可以快速得知他是在每條線的正方向或負方向,所以每個區塊都可以用長度至多 30 的元素只含 0,1 的 vector 表示,每跨越一個邊就是 vector 上某個 0 變成 1。用這樣的概念的話可以很好想很好寫
不過我所謂的很好想好好寫 …應該是在同時都曾經寫過我這方法和你那方法再來比較的話我是覺得這個方法比較好寫 …第一次寫的話或許還是要思考許久
實做的話可以對於每條直線,求出所有其他直線與他的交點,sort這些交點後,枚舉相鄰兩個交點的中點,求出該點對於其他所有直線是落在正區域或負區域,於是我們就知道只有該直線正負區域不同的兩個 vector 是相鄰的,於是就把所有邊建出來可以 bfs 了

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define eps 1e-8
#define MAXM 32767
struct Pt {
double x, y;
int label;
Pt(double a = 0, double b = 0):
x(a), y(b) {}
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 a) const {
return Pt(x * a, y * a);
}
bool operator<(const Pt &a) const {
if (fabs(x - a.x) > eps)
return x < a.x;
if (fabs(y - a.y) > eps)
return y < a.y;
return false;
}
bool operator==(const Pt &a) const {
return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
}
};
double dot(Pt a, Pt b) {
return a.x * b.x + a.y * b.y;
}
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);
}
double cross2(Pt a, Pt b) {
return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
Pt s, e;
double angle;
int label;
Seg(Pt a = Pt(), Pt b = Pt()):s(a), e(b) {
angle = atan2(e.y - s.y, e.x - s.x);
}
bool operator<(const Seg &other) const {
if (fabs(angle - other.angle) > eps)
return angle > other.angle;
if (cross(other.s, other.e, s) > -eps)
return true;
return false;
}
double interpolate(double x) const {
Pt p1 = s, p2 = e;
if (p1.x == p2.x) return p1.y;
return p1.y + (double)(p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
}
};
int cmpZero(double v) {
if (fabs(v) > eps) return v > 0 ? 1 : -1;
return 0;
}
Pt getIntersect(Seg a, Seg b) {
Pt u = a.s - b.s;
double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
return a.s + (a.e - a.s) * t;
}
int intersection(Pt a, Pt b, Pt c, Pt d) { // seg(a, b) and seg(c, d)
return cmpZero(cross(a, c, b)) * cmpZero(cross(a, b, d)) > 0
&& cmpZero(cross(c, a, d)) * cmpZero(cross(c, d, b)) > 0;
}
#define MAXH 100.0f
#define MAXW 100.0f
int validPos(double x, double y) {
return 0 <= x && x <= MAXH
&& 0 <= y && y <= MAXW;
}
struct CMP {
static double x;
double interpolate(const Pt& p1, const Pt& p2, double& x) {
if (p1.x == p2.x) return p1.y;
return p1.y + (double)(p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
}
bool operator()(const Seg &i, const Seg &j) {
double v1 = interpolate(i.s, i.e, x), v2 = interpolate(j.s, j.e, x);
if (fabs(v1 - v2) > eps)
return v1 < v2;
return false;
}
};
double CMP::x = 0;
class DisjointSet {
public:
int parent[MAXM];
int findp(int x) {
return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
x = findp(x), y = findp(y);
if (x == y) return 0;
parent[x] = y;
return 1;
}
void init(int n) {
for (int i = 0; i <= n; i++)
parent[i] = i;
}
};
class PartitionMap {
public:
int n;
DisjointSet disjointSet;
Seg segs[1024];
vector<double> X;
vector<int> g[MAXM];
set<Seg, CMP> tree[MAXM];
vector<Pt> dual[MAXM];
vector<Seg> dualLBound[MAXM], dualUBound[MAXM];
vector<Pt> pts;
void partition() {
X.clear();
for (int i = 0; i < n; i++) {
X.push_back(segs[i].s.x);
X.push_back(segs[i].e.x);
for (int j = i+1; j < n; j++) {
if (intersection(segs[i].s, segs[i].e, segs[j].s, segs[j].e)) {
Pt p = getIntersect(segs[i], segs[j]);
if (validPos(p.x, p.y)) {
X.push_back(p.x);
}
}
}
}
sort(X.begin(), X.end());
int m = 1;
for (int i = 1; i < X.size(); i++) {
if (fabs(X[i] - X[m - 1]) > eps)
X[m++] = X[i];
}
X.resize(m);
for (int i = 0; i < m; i++)
tree[i].clear();
}
void buildMap() {
int m = X.size();
int region = 0;
for (int i = 0; i < m; i++) {
dual[i].clear();
dualLBound[i].clear();
dualUBound[i].clear();
}
pts.clear();
for (int i = 0; i < m - 1; i++) {
double mid = (X[i] + X[i+1])/2;
CMP::x = mid;
for (int j = 0; j < n; j++) {
double sx = segs[j].s.x, ex = segs[j].e.x;
if (sx <= X[i] && X[i+1] <= ex) {
tree[i].insert(segs[j]);
}
}
set<Seg, CMP>::iterator it = tree[i].begin(), jt = it;
jt++;
for (; it != tree[i].end() && jt != tree[i].end(); it++, jt++) {
double a = (*it).interpolate(mid);
double b = (*jt).interpolate(mid);
double c = (a + b) /2.0;
Pt p(mid, c);
p.label = region++;
dual[i].push_back(p);
dualLBound[i].push_back(*it);
dualUBound[i].push_back(*jt);
pts.push_back(p);
}
}
// printf("region %d\n", region);
disjointSet.init(region);
vector<int> tmpg[MAXM];
for (int i = 0; i < m; i++) {
for (int j = 1; j < dual[i].size(); j++) {
int x = dual[i][j].label;
int y = dual[i][j-1].label;
tmpg[x].push_back(y);
tmpg[y].push_back(x);
}
}
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < dual[i].size(); j++) {
for (int k = 0; k < dual[i+1].size(); k++) {
double y1, y2, y3, y4;
y1 = dualLBound[i][j].interpolate(X[i+1]);
y2 = dualUBound[i][j].interpolate(X[i+1]);
y3 = dualLBound[i+1][k].interpolate(X[i+1]);
y4 = dualUBound[i+1][k].interpolate(X[i+1]);
if (max(y1, y3) < min(y2, y4)) {
// printf("%lf %lf, %lf %lf\n", y1, y2, y3, y4);
// getchar();
Pt p(X[i+1], (max(y1, y3) + min(y2, y4))/2);
int ok = 1;
for (int t = 0; t < n && ok; t++) {
if (onSeg(segs[t].s, segs[t].e, p))
ok = 0;
}
if (ok)
disjointSet.joint(dual[i][j].label, dual[i+1][k].label);
else {
tmpg[dual[i][j].label].push_back(dual[i+1][k].label);
tmpg[dual[i+1][k].label].push_back(dual[i][j].label);
}
}
}
}
}
for (int i = 0; i < region; i++)
g[i].clear();
for (int i = 0; i < region; i++) {
int x = disjointSet.findp(i);
for (int j = 0; j < tmpg[i].size(); j++) {
int y = disjointSet.findp(tmpg[i][j]);
g[x].push_back(y);
}
}
int diff = 0;
for (int i = 0; i < region; i++) {
sort(g[i].begin(), g[i].end());
g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin());
if (g[i].size())
diff++;
}
// printf("diffffffff %d\n", diff);
}
int findLocation(Pt p) {
set<Seg>::iterator it, jt;
for (int i = 0; i < X.size() - 1; i++) {
if (X[i] <= p.x && p.x <= X[i+1]) {
double mid = (X[i] + X[i+1])/2;
CMP::x = mid;
it = tree[i].lower_bound(Seg(p, p));
jt = it, jt--;
double a = (*it).interpolate(mid);
double b = (*jt).interpolate(mid);
double c = (a + b) /2.0;
for (int j = 0; j < dual[i].size(); j++) {
if (dual[i][j] == Pt(mid, c))
return disjointSet.findp(dual[i][j].label);
}
}
}
return -1;
}
int path(Pt p, Pt q) {
int st = findLocation(p);
int ed = findLocation(q);
map<int, int> dist;
queue<int> Q;
Q.push(st), dist[st] = 0;
// printf("st %d ed %d\n", st, ed);
while (!Q.empty()) {
int u = Q.front(), d = dist[u] + 1;
Q.pop();
// printf("%d %lf %lf, dist %d\n", u, pts[u].x, pts[u].y, d);
if (u == ed) return d - 1;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (dist.count(v)) continue;
dist[v] = d, Q.push(v);
// printf("%d -> %d\n", u, v);
}
}
return -1;
}
void init(Seg A[], int n) {
for (int i = 0; i < n; i++)
this->segs[i] = A[i];
this->n = n;
for (int i = 0; i < n; i++) {
if (segs[i].e < segs[i].s)
swap(segs[i].s, segs[i].e);
}
partition();
buildMap();
}
} mMap;
int main() {
int testcase, n;
double sx, sy, ex, ey;
Seg segs[128];
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lf %lf %lf %lf", &sx, &sy, &ex, &ey);
segs[i] = Seg(Pt(sx, sy), Pt(ex, ey));
}
// inter map
segs[n] = Seg(Pt(0, 0), Pt(MAXH, 0)), n++;
segs[n] = Seg(Pt(MAXH, 0), Pt(MAXH, MAXW)), n++;
segs[n] = Seg(Pt(MAXH, MAXW), Pt(0, MAXW)), n++;
segs[n] = Seg(Pt(0, MAXW), Pt(0, 0)), n++;
// outer map
int GAP = 10;
segs[n] = Seg(Pt(-GAP, -GAP), Pt(MAXH + GAP, -GAP)), n++;
segs[n] = Seg(Pt(MAXH + GAP, -GAP), Pt(MAXH + GAP, MAXW + GAP)), n++;
segs[n] = Seg(Pt(MAXH + GAP, MAXW + GAP), Pt(-GAP, MAXW + GAP)), n++;
segs[n] = Seg(Pt(-GAP, MAXW + GAP), Pt(-GAP, -GAP)), n++;
mMap.init(segs, n);
scanf("%lf %lf", &sx, &sy);
int ret = mMap.path(Pt(sx, sy), Pt(-GAP/2, -GAP/2));
printf("Number of doors = %d\n", ret);
if (testcase)
puts("");
}
return 0;
}
/*
2
7
20 0 37 100
40 0 76 100
85 0 0 75
100 90 0 90
0 71 100 61
0 14 100 38
100 47 47 100
54.5 55.4
7
20 0 37 100
40 0 76 100
85 0 0 75
100 90 0 90
0 71 100 61
0 14 100 38
100 47 47 100
1 1
*/