1183 : 消除隐藏线
- 时间限制Time Limit
- 1 秒Sec
- 内存限制Memory Limit
- 128 兆MB
- 提交次数Submitted
- 59 次Times
- 通过次数Solved
- 17 次Times
标准评测 Standard
从标准输入读入,结果写到标准输出。评测将输出拆成 token,与标准答案逐项比较,不按整段逐字节比对。
Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
| 时间与内存Time and memory | 记这一份程序的 CPU 时间和内存峰值。题目上的时间限制、内存限制就是这一份的上限。The record is this program’s CPU time and peak memory. The limits on the problem apply to this one run. |
题目描述Description
在计算机辅助设计(CAD)中,有一个经典问题:消除隐藏线(被其它图形遮住的线段)。你需要设计一个软件,帮助建筑师绘制城市的侧视轮廓图。为了方便处理,限定所有的建筑物都是矩形的,而且全部建立在同一水平面上。每个建筑物用一个三元组表示(Li, Hi, Ri)其中 Li 和 Ri 分别是建筑物 i 的左右边缘坐标,Hi 是建筑物 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)
输入格式Input
多组测试数据,每组数据第一行整数 n 表示建筑物三元组个数。
接下来 n 行,每行 3 个整数表示一个建筑物的三元组 (Li, Hi, Ri) 。建筑物的坐标都是正整数且不大于 1000
三元组按 Li 从小到大顺序给出,即左边缘坐标最小的建筑物三元组会出现在每组数据的第一个。
1 <= n <= 50。
输出格式Output
每组数据输出一行描述轮廓线的数值序列,其中偶元素代表轮廓线的延伸高度,奇元素代表轮廓线顶点的水平坐标,如上面的图例所示。
样例Sample
来源Source
湖南省第一届大学生计算机程序设计竞赛(HNCPC2005)
题目到此结束End of problem