ACM 105 The Skyline Problem

先找出x=i~i+1區段的各個高度最大值，相鄰的兩最大值會有兩種情況：相等和不相等。如果相等，則代表兩個區段的最大值相同，亦即兩處的輪廓線是同高度的，那麼我們就繼續比較相鄰兩最大值。如果不相等，則代表兩個區段的輪廓線具有高度差，此時兩區段的共同x值剛好就是題目要我們輸出的垂直Vi，接著就輸出y的最大值以及共同的x值，再繼續比較相鄰兩最大值。因此只要判斷相鄰兩最大值是否相同，若相同就做紅字的動作，若不同則做出藍字的動作。



#include <stdio.h>

int main(void)
{
    short a[10001] = {0}, min_x, max_x, h, left, right, i;
   
    /* 以a[i]表示x座標為i-1~i的最大高度 */
    scanf("%hd%hd%hd", &min_x, &h, &max_x);
    for (i = min_x+1; i <= max_x; i++)
        a[i] = h;
    while (scanf("%hd%hd%hd", &left, &h, &right) == 3)
    {
        if (right > max_x)
            max_x = right;
        for (i = left+1; i <= right; i++)
            if (h > a[i])
                a[i] = h;
    }
    printf("%hd ", min_x);
    for (i = min_x+1; i <= max_x; i++)
    {
        while (a[i] == a[i+1])
            i++;
        printf("%hd %hd ", a[i], i);
    }
    printf("0\n");
   
    return 0;
}