高中生程式解題系統(An Online Judge System For Beginners) -- 題目內容

d424: Q105: The Skyline Problem

關鍵字： ACM 105

Content ： 正體->简体

由於高速繪圖電腦工作站的出現，CAD（computer-aided design）和其他領域（CAM,VLSI設計）都充分使用這些電腦的長處。而在本問題中，你必須幫助建築師，根據他所提供給你都市中建築物的位置，你得幫他找出這些建築物的空中輪廓（skyline）。為了使問題容易處理一些，所有的建築物都是矩形的，並且都建築在同一個平面上。你可以把這城市看成一個二度平面空間。每一棟建築物都以(L_i H_i R_i)這樣的序列來表示。其中L_i 和 R_i分別是該建築物左邊和右邊的位置，H_i則是建築物的高度。下方左圖就是(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)這八棟建築物的位置圖。而你的任務就是畫出這些建築物所構成的輪廓，並且以(1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)這樣的序列來表示如下方右圖的輪廓。

Input ：

只有一組測試資料。

每列有一棟建築物的資料。建築物不會超過5000棟。所有的數字都小於10000。並且建築物已按照L_i排好序。

Output ：

輸出為描述建築物輪廓的向量。在輪廓向量（v₁,v₂,v₃,......,v_n-1,v_n）中，在i為奇數的情形下，v_i表示一條垂直線（x座標），在i為偶數的情形下，v_i表示一條水平線（高度）。輪廓向量就像一隻蟲從最左邊建築物走起，沿著輪廓路徑水平及垂直的行走的路徑。所以最後輪廓向量的最後一個數一定為0。

請參考Sample Output。

Sample Input ： help

若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。

Sample Output ：

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Hint ：

※Lucky貓翻譯

※測資很難生，可能會有錯誤

Author ：

ACM 105 (管理員：morris1028)

Solve it! Status Forum Rank