d424: 00105 - The Skyline Problem
Tags :
Accepted rate : 234人/290人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-14 00:45

Content
由於高速繪圖電腦工作站的出現,CAD(computer-aided design)和其他領域(CAM,VLSI設計)都充分使用這些電腦的長處。而在本問題中,你必須幫助建築師,根據他所提供給你都市中建築物的位置,你得幫他找出這些建築物的空中輪廓(skyline)。為了使問題容易處理一些,所有的建築物都是矩形的,並且都建築在同一個平面上。你可以把這城市看成一個二度平面空間。每一棟建築物都以(Li Hi Ri)這樣的序列來表示。其中LiRi分別是該建築物左邊和右邊的位置,Hi則是建築物的高度。下方左圖就是(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排好序

Output

輸出為描述建築物輪廓的向量

在輪廓向量(v1,v2,v3,......,vn-1,vn)中

在 i 為奇數的情形下

v表示一條垂直線(x 座標)

在 i 為偶數的情形下

v表示一條水平線(高度)

輪廓向量就像一隻蟲從最左邊建築物走起

沿著輪廓路徑水平及垂直的行走的路徑

所以最後輪廓向量的最後一個數一定為 0

請參考 Sample Output

Sample Input
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
Sample Output
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :

※Lucky貓  翻譯

 

Tags:
出處:
UVa105 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」