瑞の資訊備忘錄

一、目的：隨著高速繪圖工作站、CAD(電腦輔助設定)和其他領域(CAM,VLSI design)的出現讓電腦愈

            來愈具有影響力。其中之一的問題就是如何在繪圖時排除隱藏線(hidden lines)的問題而所謂

            的隱藏線即該線段必須被其他繪圖的部份所遮蔽。  (連結UVa online原文題庫)

二、問題說明：

     如何設計一個程式來幫助一位建築師從所給建築物在城市中的位置去繪製一個城市的天際線。

     為了讓這個問題更容易處理則所有的建築物形成都是矩形且它們都是在共同的底部。這個城市

     是一個二維度觀點，因此所有的建築物是由三個資料項(L,H,R)所定義。L、R表示建築物左、右的

     座標位置，H表示建築物的高度。 參考圖如下：

      圖左: (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)   

三、輸入與輸出說明：

     輸入的資料是一系列三個整數為一組的資料，每組資料內的整數以一個空白字元為間隔。

     輸入資料的限制或條件如下：

     1. 所有建築物的座標值是小於10，000

     2. 1<= 建築物數量 <=5000

     3. 輸入資料都是依照建築物的左邊座標由小到大排序   

     輸出結果使用一組數值所構成的向量來表示處理後的天際線，該向量中偶數位置的數值表

     示建築物的左邊座標，奇數位置中的數值表示建築物的高度。   

EX:  Sample Input                     Sample Output

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

       2 6 7

       3 13 9

       12 7 16

       14 3 25

       19 18 22

       23 13 29

       24 4 28

四、演算法說明：

4-1、如果在不考慮執行速度的情況下，使用一個巨大的整數陣列來記錄每一個點的高度並且

                更新每次新增區段之間中點的高度。

        4-2、如果在考慮執行速度的情況下，將記錄的方式由點改成區段來加快執行速度；因此使用

                 串列來表示每個不同高度的區段資料且每個區段只需記錄的起始位置及高度。

                4-2.1：判斷新區段的起始置是否大於目前已知區段的最大結尾位置。

                4-2.2：從目前區段中找到適當的位置並將新區段加入該位置中。

4-2.3：當新區段加入該位置後，對目前所有在新區段的起始位置到結尾位置之間的區

                          段進行調整。

Run time of UVa online web by algorithm 1: 0.024 sec

Run time of UVa online web by algorithm 2: 0.008 sec

Download : UVa105_TheSkylineProblem.tar.gz

Result：