UVa 904 - Overlapping Air Traffic Control Zones

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
5
1 1 1 3 3 3
1 1 1 3 3 3
1 1 1 3 3 3
400000000 400000000 400000000 400000001 400000001 400000002
400000000 400000000 400000000 400000002 400000004 400000001

Sample Output

1
9

Solution

離散化 X Y Z 軸出現的座標值,壓縮成 n * n * n 的三維陣列,接著將每一台飛機的安全範圍離散化後,將其所在的位置進行標記。

離散化後,每一格將會具有不同的長度,把離散的數據聚集在一起,而事實上在工程數學中,離散化一詞則是將連續的數據變成整數離散的情況。

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
#include <stdio.h>
#include <map>
using namespace std;
#define MAXN 32
void mapRelabel(map<int, int> &R, int val[]) {
int size = 0;
for (map<int, int>::iterator it = R.begin();
it != R.end(); it++) {
val[size] = it->first;
it->second = size++;
}
}
int main() {
int n;
int lx[MAXN], ly[MAXN], lz[MAXN];
int rx[MAXN], ry[MAXN], rz[MAXN];
int xval[MAXN], yval[MAXN], zval[MAXN];
while (scanf("%d", &n) == 1) {
map<int, int> RX, RY, RZ;
for (int i = 0; i < n; i++) {
scanf("%d %d %d", &lx[i], &ly[i], &lz[i]);
scanf("%d %d %d", &rx[i], &ry[i], &rz[i]);
RX[lx[i]] = RX[rx[i]] = 1;
RY[ly[i]] = RY[ry[i]] = 1;
RZ[lz[i]] = RZ[rz[i]] = 1;
}
mapRelabel(RX, xval);
mapRelabel(RY, yval);
mapRelabel(RZ, zval);
int a = RX.size(), b = RY.size(), c = RZ.size();
int sx, ex, sy, ey, sz, ez;
int cnt[MAXN][MAXN][MAXN] = {};
for (int i = 0; i < n; i++) {
sx = RX[lx[i]], ex = RX[rx[i]];
sy = RY[ly[i]], ey = RY[ry[i]];
sz = RZ[lz[i]], ez = RZ[rz[i]];
for (int p = sx; p < ex; p++) {
for (int q = sy; q < ey; q++) {
for (int r = sz; r < ez; r++) {
cnt[p][q][r]++;
}
}
}
}
int ret = 0;
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
for (int k = 0; k < c; k++) {
if (cnt[i][j][k] >= 2) {
ret += (xval[i+1] - xval[i]) * (yval[j+1] - yval[j]) * (zval[k+1] - zval[k]);
}
}
}
}
printf("%d\n", ret);
}
return 0;
}