BZPRO

#3089. Coci2009 ograda

内存限制：128 MiB 时间限制：3 Sec
提交 提交记录 讨论

题目描述

给定平面里的 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

数据范围与提示

BZPRO Powered by Remmina.
Github Repository