分数: 200 点
问题陈述
在一家工厂里,有 N 机器人放置在数轴上。 机器人 i 放置在坐标处 X_i 并且可以延伸其长度 L_i 正负两个方向。
我们想要移除零个或多个机器人,以便剩余两个机器人的手臂可移动范围不相交。 在这里,对于每一个 i (1 \leq i \leq N), 机器人手臂可动范围 i 是坐标之间的数轴部分 X_i - L_i 和 X_i + L_i,不包括端点。
找出我们可以保留的机器人的最大数量。
约束
- 1 \leq N \leq 100,000
- 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_i \leq 10^9 (1 \leq i \leq N)
- If i \neq j, X_i \neq X_j.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N X_1 L_1 X_2 L_2 \vdots X_N L_N
输出
打印我们可以保留的机器人的最大数量。
示例输入 1
4 2 4 4 3 9 3 100 5
示例输出 1
3
通过移除机器人 2,我们可以保留其他三个机器人。
示例输入 2
2 8 20 1 10
示例输出 2
1
示例输入 3
5 10 1 2 1 4 1 6 1 8 1
示例输出 3
5