bzoj#P3089. Coci2009 ograda
Coci2009 ograda
题目描述
给定平面里的 个矩形,每个矩形的边都是和坐标系平行的。
并且满足每个矩形的下面的边和 轴重合。
从 个矩形中删除最多的矩形,使得矩形并的区域的边界保持不变。
输入格式
第 行一个整数 。
第 到 行,每行 个整数 ,表示一个矩形。
表示矩形左边界的 坐标。
表示矩形的宽度(右边的 坐标 左边的 坐标)。
表示矩形的高度(上边的 坐标 下边的 坐标)。
没有两个矩形是完全重合( 都完全一样)的。
所有矩形从 到 标号。
输出格式
一行,最少留下的矩形数量 。
6
15 8 4
10 8 3
25 3 7
3 9 5
1 5 3
7 2 2
5
数据规模与约定
对于 的数据,,。