地平線上有許多房子，而這些房子在夕陽的照射之下形成有趣的輪廓，我們稱之為天際線(Skyline)。
為了方便起見，你可以假設所有的房子都是一個位在2D平面上的矩形，並且有一條邊貼在這個假想2D平面上的X軸。
一棟建築可以用三元數組(Li,Hi,Ri)來表示，依序代表該建築物的左界座標、高度、右界座標。下方左圖中的八棟建築就是用此方法表示就是(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)。
一個天際線也可以用類似的「X-遞增序列」表示出來，例如上面的八棟建築合併之後上方右圖的天際線可表示為：
(1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)
請你寫一個程式，給你這些房子的位置，請你把它們形成的天際線描述出來。
請注意，最後一個數字一定是0。也請不要輸出多餘空白。
$n\le 30000, L_i\le R_i, 1\le L_i,R_i,H_i\le 10^9$
天際線的定義其實就是找出每個x上的房子高度最大值，如果跟前一格不一樣就記錄下來。
可能會發生最大高度變動的只有每個房子的左右界，所以就先記錄下來，將房子按左界排序，然後就能掃描線了。
之後維護一個隨右界遞減的單調對列，不過右界並沒有單調性，所以得用map之類的結構。
先將左邊右界小於當前座標的房子都pop掉，之後加入左界為當前座標的房子。
加入一棟房子時，先檢查它右邊第一個是否比它大，如果比它大那這個房子就用不到，否則就插入，插入後還得將它左邊比它小的都pop掉。
每個點的最大值就會是隊列的首項，一開始先插入[INF, 0]，這樣在沒房子時高度會視為0。
時間複雜度：因為左右界最多只會有$2n$個，所以只會迭代$\mathcal{O}(n)$次，配上map的複雜度，總共$\mathcal{O}(nlogn)$。
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
map<int, int> cur;
struct seg {
int l, r, y;
bool operator<(seg &b) {return l==b.l ? r<b.r : l<b.l;}
};
void add(int y, int r) {
auto it = cur.lower_bound(r);
if(it->second >= y)
return;
it = cur.upper_bound(r);
while(it != cur.begin()) {
it--;
if(it->second <= y)
it = cur.erase(it);
else
break;
}
cur[r] = y;
}
signed main() {
EmiliaMyWife
int n;
while(cin >> n, n) {
cur.clear();
vector<seg> arr(n);
vector<int> v;
for(int i = 0; i < n; i++) {
cin >> arr[i].l >> arr[i].y >> arr[i].r;
v.push_back(arr[i].l);
v.push_back(arr[i].r);
}
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
sort(arr.begin(), arr.end());
vector<pair<int, int>> ans;
int prv = 0, it = 0;
cur[INF] = 0;
for(int i : v) {
if(cur.count(i))
cur.erase(i);
while(it < n && arr[it].l == i) {
add(arr[it].y, arr[it].r);
it++;
}
if(cur.begin()->second != prv)
ans.push_back({i, prv = cur.begin()->second});
}
for(int i = 0; i < ans.size(); i++)
cout << ans[i].first << ' ' << ans[i].second << " \n"[i + 1 == ans.size()];
}
return 0;
}
|