#P1382. 楼房

    ID: 426 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>线段树二叉堆福建省历届夏令营

楼房

题目描述

地平线(xx 轴)上有 nn 个楼房,每个楼房可以表示为一个矩形。

用三个整数 hi,li,rih_i,l_i,r_i 来表示第 ii 个矩形:矩形左下角为 (li,0)(l_i,0),右上角为 (ri,hi)(r_i,h_i)

地平线高度为 00。在轮廓线长度最小的前提下,从左到右输出轮廓线。

输入格式

第一行一个整数 nn,表示矩形个数。

以下 nn 行,每行 33 个整数 hi,li,rih_i,l_i,r_i 表示第 ii 个矩形。

输出格式

第一行一个整数 mm,表示节点个数。

以下 mm 行,每行一个坐标表示轮廓线上的节点。

要求从左到右遍历轮廓线并顺序输出节点。

注:第一个和最后一个节点的 yy 坐标必然为 00

2
3 0 2
4 1 3

6
0 0
0 3
1 3
1 4
3 4
3 0
5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8
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

提示

样例二如图:

数据范围:

对于 30%30\% 的数据,n100n\le100

对于另外 30%30\% 的数据,1hi,li,ri10001\le h_i,l_i,r_i\le 1000

对于 100%100\% 的数据,1n1051\le n\le10^51hi1091\le h_i\le 10^9109li<ri109-10^9\le l_i<r_i\le10^9