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. |
题目描述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
每组数据输出一行描述轮廓线的数值序列,其中偶元素代表轮廓线的延伸高度,奇元素代表轮廓线顶点的水平坐标,如上面的图例所示。