【解題】The Skyline Problem

ACM Volume I 105 - The Skyline Problem


Background

With the advent of high speed graphics workstations, CAD (computer-aided design) and other areas (CAM, VLSI design) have made increasingly effective use of computers. One of the problems with drawing images is the elimination of hidden lines -- lines obscured by other parts of a drawing.


The Problem

You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. To make the problem tractable, all buildings are rectangular in shape and they share a common bottom (the city they are built in is very flat). The city is also viewed as two-dimensional. A building is specified by an ordered triple (L_i, H_i, R_i) where L_i and R_i are left and right coordinates, respectively, of building i and H_i is the height of the building. In the diagram below buildings are shown on the left with triples (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)

the skyline, shown on the right, is represented by the sequence: (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0).




The Input

The input is a sequence of building triples. All coordinates of buildings are positive integers less than 10,000 and there will be at least one and at most 5,000 buildings in the input file. Each building triple is on a line by itself in the input file. All integers in a triple are separated by one or more spaces. The triples will be sorted by R_i, the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input file.


The Output

The output should consist of the vector that describes the skyline as shown in the example above. In the skyline vector (v₁, v₂, v₃, ..., v_n-2, v_n-1, v_n) , the v_i such that i is an even number represent a horizontal line (height). The v_i such that i is an odd number represent a vertical line (x-coordinate). The skyline vector should represent the ``path'' taken, for example, by a bug starting at the minimum x-coordinate and traveling horizontally and vertically over all the lines that define the skyline. Thus the last entry in the skyline vector will be a 0. The coordinates must be separated by a blank space.

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


解題思考

　　這一題我採用暴力法來解決，即是直接紀錄每個 x 座標上的最高高度，再依題目要求輸出。

　　所以，一開始我就直接根據 x 座標建立「最大高度」陣列，即 height[i] 代表 x = i 時的大樓最大高度，並在讀入每一筆大樓資料時更新這個陣列。

　　接著，用一個變數以記錄當前高度，並初始化為 0 (沒有大樓)。再利用迴圈去判斷某 x 軸的最大高度是否不等於當前高度。若是，則輸出該點的 x 座標與其高度。並於更新當前高度後繼續執行迴圈。

　　看起來好像這樣，這一題就完成了。


　　但是，讓我們先想想看，若是把 Sample Input 第六行的 (19 18 22) 改成 (19 13 22)，使之與其間隔為一的第七行大樓的 (23 13 29) 高度相同。

　　這時，如果是正確的程式輸出結果，應該要是：

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

　　結果呢，你發現實際的輸出結果竟然是：

1 11 3 13 9 0 12 7 16 3 19 13 29 0

　　怎麼了？為什麼會錯呢？

　　主因是因為，以目前的紀錄法在讀入第六行的 (19 13 22) 時，height[19] 至 height[22] 的值會被更新為 13。而在讀入第七行的 (23 13 29) 時，height[23] 至 height[29] 的值會也被更新為 13。

　　(哎呀！)看出問題了嗎？在利用迴圈檢查當前高度是否相等時，由於 height[22] 與 height[23] 的值都是 13，所以原本像這樣子的結果：



　　就會被誤判為下面這樣：




　　那麼該怎麼解決呢？

　　其實，只要將 height[i] 的意義改成「介在 x = i 與 x = i + 1 間的最大高度」。

　　就這麼簡單，就可以修正這個問題囉。


參考解答(C++)

#include <iostream>

#define MAX_WEIGHT 10000

using namespace std;

int main(void)
{
    int height[MAX_WEIGHT + 1];
    memset(height, 0, sizeof(int) * (MAX_WEIGHT + 1));

    // 直接紀錄每個 x 的最大高度
    int l, h, r, bound = 0;
    while (cin >> l >> h >> r)
    {
        if (r > bound) { bound = r; }

        for (int i = l; i < r; i++)
        {
            if (h > height[i])
            {
                height[i] = h;
            }
        }
    }

    int current = 0;
    for (int i = 0; i < bound; i++)
    {
        // 尋找不同於當前高度的位置
        if (height[i] != current)
        {
            cout << i << " " << height[i] << " ";
            current = height[i];
        }
    }

    cout << bound << " " << height[bound] << endl;

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}