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)
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA105/889bd37f0f1c53beef16050923d5dea72240646d.png)
输入输出格式
输入格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA105/a2ec38ede793360654026cc6d2ebc8d4ff3613a3.png)
输出格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA105/fce0a3209462c25fc24ce11d947d1827d467d35d.png)
输入输出样例
输入样例 #1
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
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0