bzoj#P3089. Coci2009 ograda

Coci2009 ograda

题目描述

给定平面里的 nn 个矩形,每个矩形的边都是和坐标系平行的。

并且满足每个矩形的下面的边和 xx 轴重合。

nn 个矩形中删除最多的矩形,使得矩形并的区域的边界保持不变。

pic1

输入格式

11 行一个整数 nn

22n+1n+1 行,每行 33 个整数 x,w,hx,w,h,表示一个矩形。

xx 表示矩形左边界的 xx 坐标。

ww 表示矩形的宽度(右边的 xx 坐标 - 左边的 xx 坐标)。

hh 表示矩形的高度(上边的 yy 坐标 - 下边的 yy 坐标)。

没有两个矩形是完全重合(x,w,hx,w,h 都完全一样)的。

所有矩形从 11nn 标号。

输出格式

一行,最少留下的矩形数量 bb

6
15 8 4
10 8 3
25 3 7
3 9 5
1 5 3
7 2 2
5

数据规模与约定

对于 100%100\% 的数据,1n1051\le n\le 10^50x,w,h1090\le x,w,h\le 10^9