← 返回题目列表

AtCoder · keyence2020_b

B. 机器人手臂

中文机器翻译题面 查看原题

分数: 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