华师一附中OI组

标题: P1904 天际线 [打印本页]

作者: admin 时间: 2018-9-29 16:27
标题: P1904 天际线
https://www.luogu.org/problemnew/show/P1904

题目描述
Latium省的Genoa是亚平宁半岛西海岸北端的一片土地，自然资源丰富，却无人居住。你受到罗马执政官Caesar的委任，前往Genoa建立新的城市。Caesar对这次任务的要求是在Genoa这片土地上建立起一座繁荣的城市，他将以此作为衡量你的表现的标准。

正在你大刀阔斧地进行城市建设的时候，Caesar突然写信给你，说他要检查Genoa的建设情况。Caesar希望知道你的城市是什么样子，但是他又非常的忙，所以他只要你描述一下城市的轮廓就可以了，他将依照城市的轮廓决定你的薪水。

怎样描述一个城市的轮廓呢？我们知道Genoa所有的建筑共享一个地面，你可以认为它是水平的。所有的建筑用一个三元组（Li,Hi,Ri）其中Li和Ri分别是建筑的左坐标和右坐标，Hi就是建筑的高度。在下方所示的图表中左边建筑物描述如下(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的正整数，且至少有1幢建筑，最多有5,000幢建筑。在输入输入中每幢建筑的三元组各占一行。三元组中的所有整数应由一个或多个空格分开。

输出格式：
在输出数据中，你被要求给出城市的轮廓线。你可以这样来描述：对于所有轮廓线上的折点，按顺序排好，第奇数个点输出x坐标，第偶数个点输出y坐标，两个数之间用空格分开。

输入输出样例
输入样例#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

欢迎光临华师一附中OI组 (http://hsyit.cn/)