ACM 105 The Skyline Problem

本來想直接做，但是要考慮很多很多問題。
就算是input已經sorted，要考慮起始點跟終點。
起始點是否相等，紀錄前後起始點；
終點處理，暫存等等等……頭都昏惹。

後來看到神人的解法……只有佩服兩個字可以形容。
首先我們已知最高高度跟最長長度。
假設一開始只有一塊土地，啥建築物都沒有。
現在每吃到一筆資料（一棟建築物），就更新我們的skyline，
如此，隨著建築物不停的增加，天際線也會不斷的改變。
最後再輸出天際線即可。
真是個強大的方法……

/* ACM 105 The Skyline Problem
 * mythnc
 * 2012/01/07 09:19:19   
 * run time: 0.02
 */
#include <stdio.h>

#define MAXH 10000

typedef struct build {
    int s, e, h;
} Build;

void update(Build);
void print(void);

int sky[MAXH];

int main(void)
{
    Build x;

    while (scanf("%d %d %d", &x.s, &x.h, &x.e) == 3)
        update(x);
    print();

    return 0;
}

/* update: update sky line */
void update(Build x)
{
    int i;

    for (i = x.s; i < x.e; i++)
        if (x.h > sky[i])
            sky[i] = x.h;
}

/* print: print out result */
void print(void)
{
    int i, h;

    /* find the first building */
    for (i = h = 0; i < MAXH; i++)
        if (sky[i] != h) {
            printf("%d %d", i, sky[i]);
            h = sky[i];
            break;
        }
    for (; i < MAXH; i++)
        if (sky[i] != h) {
            printf(" %d %d", i, sky[i]);
            h = sky[i];
        }
    putchar('\n');
}