#P3089. Coci2009 ograda

    ID: 2244 传统题 1000ms 512MiB 尝试: 20 已通过: 10 难度: 6 上传者: 标签>CF2100提高扫描线区间覆盖堆贪心懒删除交换论证同时事件分阶段处理

Coci2009 ograda

题目描述

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

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

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

pic1

输入格式

第 11 行一个整数 nn。

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

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

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

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

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

所有矩形从 11 到 nn 标号。

输出格式

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

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

数据规模与约定

对于 100%100\% 的数据,1≤n≤1051\le n\le 10^5,0≤x,w,h≤1090\le x,w,h\le 10^9。