解題區/解題區 - UVa

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