← 返回题目列表

Codeforces · 35/E

E. 游行

中文机器翻译题面 查看原题

贝尔兰的伟大胜利周年纪念日从来没有没有阅兵式过。今年也不例外。这就是为什么准备工作正在全力进行。坦克正在排成一列,火炮准备开火,士兵们正在主广场上行进……而空军将军格杰洛夫先生又遇到了麻烦。今年建了很多摩天大楼,导致飞机很难在城市上空飞行。决定飞机严格从南向北飞行。而且,飞机航线上不能有摩天大楼,否则周年纪念日将成为一场悲剧。建设部给出了n座摩天大楼的数据(其余建筑物都比较小,对飞机不会造成问题)。当从南向北将城市视为一个几何平面时,第 i 栋建筑是一个高度为 hi 的矩形。其最西点的 x 坐标为 li,最东点的 x 坐标为 ri。该地区地势平坦,所有建筑物均位于一层。作为国防部的首席程序员,您的任务是使用摩天大楼上的数据找到一条包络折线。折线的属性如下:

- 如果你从南到北将城市视为一个平面,那么任何建筑物的任何部分都将位于折线与地面一起围成的区域的内部或边界上。
- 折线在地面上开始和结束,即高度等于 0。
- 折线的线段与坐标轴平行,即它们只能是垂直或水平的。
- 折线的顶点应具有整数坐标。
- 如果从南到北观察城市,折线(连同陆地表面)必须包围尽可能小的区域。
- 多段线必须具有所有多段线中最小的长度,并包围尽可能小的土地面积。
- 多段线的连续线段必须是垂直的。

第二个示例测试的图片(包络折线标记在右侧)。

输入

第一个输入行包含整数 n (1 ≤ n ≤ 100000)。然后是 n 行,每行包含三个整数 hi、li、ri (1 ≤ hi ≤ 109,- 109 ≤ li < ri ≤ 109)。

输出

在第一行中输出整数 m — 包络折线的顶点数量。接下来的 m 行应每条包含 2 个整数——折线顶点的位置和高度。按照从西向东遍历折线的顺序输出每个顶点的坐标。请记住,折线的第一个和最后一个顶点的高度应为 0。

示例

输入 #1

2
3 0 2
4 1 3

输出 #1

6
0 0
0 3
1 3
1 4
3 4
3 0

输入 #2

5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8

输出 #2

14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0