解題區/解題區 - UVa

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;
}