题目描述

给定平面里的 N 个矩形, 每个矩形的边都是和坐标系平行的. 并且满足 每个矩形的下面的边 和 x轴 重合. 从 N 个矩形中删除最多的矩形, 使得 矩形并的区域的边界 保持不变.

输入格式

第1行: 一个整数 N (1 <= N <= 100, 000)     第2..N+1行: 每行3个整数 X, W, H, 表示一个矩形.                 X 表示矩形左边界的x坐标.                 W 表示矩形的宽度 (右边的x坐标 - 左边的x坐标)                 H 表示矩形的高度 (上边的y坐标 - 下边的y坐标)                 没有两个矩形是 完全重合 (X W H 都完全一样) 的.                 0 <= X, W, H <= 10^9                 所有矩形标号为 1..N

输出格式

第1行: 最少留下的矩形数量 B

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

5

f提示

Source