d424.
00105 - The Skyline Problem
內容
由於高速繪圖電腦工作站的出現，CAD（computer-aided design）和其他領域（CAM,VLSI設計）都充分使用這些電腦的長處。而在本問題中，你必須幫助建築師，根據他所提供給你都市中建築物的位置，你得幫他找出這些建築物的空中輪廓（skyline）。為了使問題容易處理一些，所有的建築物都是矩形的，並且都建築在同一個平面上。你可以把這城市看成一個二度平面空間。每一棟建築物都以(Li Hi Ri)這樣的序列來表示。其中Li 和 Ri分別是該建築物左邊和右邊的位置，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)這樣的序列來表示如下方右圖的輪廓。 
輸入說明
只有一組測試資料
每列有一棟建築物的資料
建築物不會超過 5000 棟
所有的數字都小於 10000
並且建築物已按照 Li 排好序
輸出說明
輸出為描述建築物輪廓的向量
在輪廓向量（v1,v2,v3,......,vn-1,vn）中
在 i 為奇數的情形下
vi 表示一條垂直線（x 座標）
在 i 為偶數的情形下
vi 表示一條水平線（高度）
輪廓向量就像一隻蟲從最左邊建築物走起
沿著輪廓路徑水平及垂直的行走的路徑
所以最後輪廓向量的最後一個數一定為 0
請參考 Sample Output
範例輸入
#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
範例輸出
#1
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
公開 測資點#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
提示 ：
※Lucky貓 翻譯
標籤:
出處:
UVa105
[管理者：
morris1028
(碼畜)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||