← 返回题目列表

AtCoder · ajo2024_final_d

D. 射星

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

配点 : 1000 点

問題文

有 N 颗星星,按坐标递减顺序排列。 它们的编号最大为 1 从 N 。明星 i \ (1 \leq i \leq N) 是坐标 X_i 亮度为 A_i 。

AtCoder 想要拍摄一些明星的照片。 AtCoder 在数轴上选择一个他喜欢的区间,并拍摄其中包含的星星。在这里,照片中的多颗星星可能太亮而无法等同。这遵循以下规则。

  1. 星 i, j 是 如果\left|X_i - X_j\right| \leq A_i + A_j 满足,则相等
  2. 星 i, k 已被识别并且星星 当 k, j 被识别时,星星 i, j 等于
  3. 未按照上述规则识别的星星将在照片中显示为不同的星星。

请注意,未落在拍摄区域内的星星不会出现在照片中。甚至不需要身份识别 请注意。

现在,如果你选择好拍摄区域,你能在照片中捕捉到多少颗不同的星星? 您将获得

T 测试用例,因此请找到每个测试用例的答案。 在

制約

  • T \geq 1
  • 1 \leq N \leq 200\,000
  • 0 \leq X_1 < \dots < X_N \leq 10^8
  • 1 \leq A_i \leq 10^8
  • T 测试用例中 N 的总和是 200\,000 以下
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。这里 这意味着第 \mathrm{case}_i 为 i 个测试用例。

T
\mathrm{case}_1
\mathrm{case}_2
 \vdots
\mathrm{case}_T

每个测试用例均按以下格式给出。

N
X_1 A_1
X_2 A_2
 \vdots
X_N A_N

出力

请打印答案。


入力例 1

3
4
0 1
3 1
6 5
9 1
6
0 3
1 1
4 1
6 1
9 1
10 3
5
10 5
20 5
30 5
40 5
50 5

出力例 1

2
3
1

1 如何在测试用例中拍照 2 如下所示。

  1. 坐标是 0 以上 5 如果选择以下间隔:星形 照片中将出现 1, 2 。|X_1 - X_2| = 3, A_1 + A_2 = 2 因此,明星 1, 2 在照片中显示为一颗单独的星星。 照片中将出现
  2. 坐标是 0 以上 9 如果选择以下间隔:星形 照片中将出现 1, 2, 3, 4 。由于问题陈述中的第一条规则,星号 1, 3、星 2, 3、星 3, 4 将被等同。那么,根据问题中的第二条规则,星星 1, 2, 3, 4 被识别为一颗星。

在这个测试用例中,最多 2 可以拍成两颗不同的星星,一种方法是方法1.2.方法中 1 这不是最好的选择,因为它会在照片中显示为一颗星星。 对于第

2 个测试用例,最多 3 一种方法是指定星星的坐标。 1 以上 9 可以使用以下方法来选择间隔。 在第

3 个测试用例中,无论你如何选择包含星号的区间,1 它将在照片中显示为两颗星。