分数: 500 点
问题陈述
有 N 兔子编号
数轴上的 1 to N 。兔子 i 位于坐标处 X_i。多只兔子可能位于同一坐标。
每只兔子都有一个参数,称为 跳跃力和兔子 i 具有跳跃力 R_i.
现在,所有兔子都会跳一次。当兔子到达坐标时 x 具有跳跃力 r 跳跃,移动到坐标 x+r 或坐标 x-r.
如果你可以自由选择每只兔子跳到哪个坐标,请找出所有兔子都跳完后,兔子所在的不同坐标的最大可能数量。
约束
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq X_i \leq 10^9
- 1 \leq R_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X_1 R_1 X_2 R_2 \vdots X_N R_N
输出
输出兔子跳跃后出现的不同坐标的最大可能数量。
示例输入 1
3 4 1 2 3 4 5
示例输出 1
3
如果每只兔子如下图所示移动,就有可能实现 3 作为兔子跳跃后出现的不同坐标的数量,这是可能的最大值。
- 兔子 1 移至 4 - 1 = 3.
- 兔子 2 移至 2 + 3 = 5.
- 兔子 3 移至 4 - 5 = -1.
示例输入 2
6 2 1 3 2 6 1 5 2 4 3 4 1
示例输出 2
4
如果每只兔子如下图所示移动,就有可能实现 4 作为兔子跳跃后出现的不同坐标的数量,这是可能的最大值。
- 兔子 1 移至 2 - 1 = 1.
- 兔子 2 移至 3 + 2 = 5.
- 兔子 3 移至 6 + 1 = 7.
- 兔子 4 移至 5 + 2 = 7.
- 兔子 5 移至 4 - 3 = 1.
- 兔子 6 移至 4 - 1 = 3.
示例输入 3
10 1000000000 1000000000 1000000000 1 -1000000000 1000000000 -1000000000 1 0 1 2 1 1 2 4 1 3 2 4 3
示例输出 3
9