1202 . 重疊的天際線
TopCoder
Tags
Description
地平線上有許多房子，而這些房子在夕陽的照射之下形成有趣的輪廓，我們稱之為天際線(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)
請你寫一個程式，給你這些房子的位置，請你把它們形成的天際線描述出來。
Input Format
輸入檔可能包含多筆測試資料。
每筆測試資料的第一列有一個正整數n(1<=n<=30,000)，然後有n列，每列有三個整數Li,Hi,Ri用來描述一棟建築(Li<Ri)。所有數字都介於1和109之間(包含1以及109)。
當n=0時，代表輸入結束，請不要對它做任何處理。
Output Format
對於每一筆測試資料，請按照題目以及範例輸出格式輸出天際線的樣子。請注意，最後一個數字一定是0。也請不要輸出多餘空白。
※請保證你的輸出是所有天際線的描述當中最簡短的。
例如：(1, 100, 2, 100, 3, 100, 4, 0)是不正確的，因為X座標在1,2之間、2,3之間、3,4之間的高度都是100，沒有必要描述出來。
上面例子的正確輸出是(1, 100, 4, 0)。
Sample Input 1
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
0
Sample Output 1
Hints
Problem Source
原TIOJ1202 / TIOJ 2008例行賽02 (prob D)。adapted from: ACM 105。Problem Setter：Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 50 |
| 2 | 1 | 50 |