UVa 12109 - Fairies' Defence

contents

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

Problem

在三維空間中有 N 位仙女,突然間被攻擊者定住,而攻擊者可能在這三維方體中任何一點出現,出現時會攻擊最鄰近的仙女,請問每名仙女被攻擊的機率為何?

Sample Input

1
2
3
4
5
6
7
2 3 3 3
1 1 1
2 2 2
2 7 2 10
1 1 6
3 1 6
0

Sample Output

1
2
Case 1: 0.500 0.500
Case 2: 0.286 0.714

Solution

很明顯地是一個 3D Voronoi,但是要處理 3D Voronoi 還不太行,根據 DJWS 筆記中寫道,應該使用 O(N N log N) 的做法,窮舉一點與其他點之間拉出來的半平面交,計算半平面交的面積佔有多少。

但這一題是 3D 情況,也就是說半空間交,找到凸殼之後計算其體積,因此沒有單純的半平面交這麼簡單。

如何做到半空間交目前沒有想法,但是利用蒙地卡羅算機率還算可行,每一筆測資限制窮舉次數在 800 萬內即可通過。

由於 N 很小,也想過窮舉一點之後,拉出半空間的所有情況,任三面交一點,若該點在半空間中都符合,則保留於後面處理。得到所有點集,拿來做三維凸包,之後計算體積。關於三維凸包 (凸殼) 計算體積,內部戳一點,對於所有面會形成錐體,把所有錐體體積加總即可。

也許 DJWS 的作法是正確的,但是目前不知道如何做到半空間交。不知道要怎麼繞行算法。

關於 2D 的題目,請參考 zerojudge b358. 竹馬不敵天降

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
double mrandom() {
int r = rand();
return (double) r / RAND_MAX;
}
int main() {
int n, a, b, c;
int cases = 0;
int x[32], y[32], z[32];
while (scanf("%d", &n) == 1 && n) {
scanf("%d %d %d", &a, &b, &c);
const int runtime = 8000000;
for (int i = 0; i < n; i++)
scanf("%d %d %d", &x[i], &y[i], &z[i]);
int count[32] = {}, guess = runtime / n;
double tx, ty, tz;
for (int i = guess - 1; i >= 0; i--) {
tx = mrandom() * a, ty = mrandom() * b, tz = mrandom() * c;
double dist = 1e+60, tmp;
int mn = 0;
for (int j = 0; j < n; j++) {
tmp = (tx - x[j]) * (tx - x[j]) + (ty - y[j]) * (ty - y[j]) +
(tz - z[j]) * (tz - z[j]);
if (tmp < dist)
dist = tmp, mn = j;
}
count[mn]++;
}
printf("Case %d:", ++cases);
for (int i = 0; i < n; i++)
printf(" %.3lf", (double) count[i] / guess);
puts("");
}
return 0;
}