The Skyline Problem

随着高速图形工作站、CAD（计算机辅助设计）等领域的出现（CAM，VLSI设计）计算机的使用已经越来越有效。其中一个有关绘制图像的问题就是消除隐藏线（由画的其他部分遮蔽的线条）。 你要设计一个程序来帮助建筑师绘制一个城市的给定地点的轮廓线。 为了使问题易于处理，所有的建筑物都是矩形的。他们共用一个共同的底部（他们所建的城市非常平坦）。城市也被视为二维的。 一个建筑物是由有序三维数组 $(L_i,H_i,R_i)$ 指定的。 $L_i$ 和 $R_i$ 是建筑 $i$ 左边和右边的位置，$H_i$ 是 $i$ 的高度。 在建筑物下面的图示用三维数组表示在下面。 ``` （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） 输入 输入是构建三维数组的序列。建筑物的所有坐标是小于 $10000$ 的整数。 在输入文件中至少有一个和至多 $5000$ 个建筑物。每栋建筑三层 输入文件中的一行。三维数组中的所有整数由一个或多个空间分隔。三维数组已经按 $L_i$ 排序。 左边的 X 坐标系是最小的建筑因此 X 坐标是输入文件中的第一个。 输出 输出应该由上面描述的描述 Skyline 的向量组成。 在 Skyline 向量$(v_1,v_2,v_3,\cdots,v_{n-2},v_{n-1},v_n)$，当 $i$ 是偶数时，这表示一个水平线（高度）。当 $i$ 是一个奇数时，表示垂直线（X 坐标）。 Skyline 矢量应该代表“路径”，例如，以最小值开始的 bug。 X 坐标可以在所有定义 Skyline 线的水平和垂直方向上移动。因此所有 Skyline 矢量中的最后一个条目是 $0$。 由 @吴戈 提供翻译

【重题请见P1904】

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41 [PDF](https://uva.onlinejudge.org/external/1/p105.pdf) 



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