解題區/解題區 - UVa

UVa 221 - Urban Elevations

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
12
13
14
15
16
14
160 0 30 60 30
125 0 32 28 60
95 0 27 28 40
70 35 19 55 90
0 0 60 35 80
0 40 29 20 60
35 40 25 45 80
0 67 25 20 50
0 92 90 20 80
95 38 55 12 50
95 60 60 13 30
95 80 45 25 50
165 65 15 15 25
165 85 10 15 35
0

Sample Output

1
2
For map #1, the visible buildings are numbered as follows:
5 9 4 3 10 2 1 14

Solution

將題目轉換成區間覆蓋，只有距離近會蓋住距離遠的，同時高度比較高的才能算是遮住一個區間，否則不能算是遮蔽一個完整的區間，因為仍然會從南面看到。

最後對一個建築物，找到所有遮蔽區間，檢查是否完全遮蔽自己的區間。

檢查部分使用掃描線算法。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Building {
    int x, y;
    int width, depth, height, label;
    int in() {
        return scanf("%d %d %d %d %d", &x, &y, &width, &depth, &height) == 5;
    }
    bool operator<(const Building &a) const {
        if(make_pair(x, y) != make_pair(a.x, a.y))
            return make_pair(x, y) < make_pair(a.x, a.y);
        return depth < a.depth;
    }
}; 
int coverL(vector< pair<int, int> > interval, int l, int r) {
    sort(interval.begin(), interval.end());
    int y = l;
    for(int i = 0; i < interval.size(); i++) {
        if(interval[i].first <= y)
            y = max(y, interval[i].second);
        else
            return 0;
    }
    return y >= r;
}
void solve(Building D[], int n) {
    sort(D, D+n);
    int f = 0;
    for(int i = 0; i < n; i++) {
        vector< pair<int, int> > interval;
        for(int j = 0; j < n; j++) {
            if(j == i)	continue;
            if(D[i].height > D[j].height || D[i].y <= D[j].y)
                continue;
            int l = max(D[i].x, D[j].x), r = min(D[i].x+D[i].width, D[j].x+D[j].width);
            if(l < r)
                interval.push_back(make_pair(l, r));
        }
        if(!coverL(interval, D[i].x, D[i].x + D[i].width)) {
            if(f++)	putchar(' ');
            printf("%d", D[i].label + 1);
        }
    }
    puts("");
}
int main() {
    int n, cases = 0;
    Building D[128];
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++)
            D[i].in(), D[i].label = i;
        if(cases++)	puts("");
        printf("For map #%d, the visible buildings are numbered as follows:\n", cases);
        solve(D, n);
    }
    return 0;
}