E - Distribute Bunnies 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

1 から N の番号がついた N 匹のウサギが数直線上にいます。ウサギ i は座標 X_i にいます。同じ座標に複数のウサギがいることもあります。
ウサギは ジャンプ力 というパラメータを持っていて、ウサギ i のジャンプ力は R_i です。
これから全てのウサギがちょうど 1 回ずつジャンプします。座標 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

Score : 500 points

Problem Statement

There are N rabbits numbered 1 to N on a number line. Rabbit i is at coordinate X_i. Multiple rabbits may be at the same coordinate.
Each rabbit has a parameter called jumping power, and rabbit i has jumping power R_i.
Now, all rabbits will jump exactly once. When a rabbit at coordinate x with jumping power r jumps, it moves to coordinate x+r or coordinate x-r.
If you can freely choose which coordinate each rabbit jumps to, find the maximum possible number of distinct coordinates where rabbits are present after all rabbits have jumped.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq X_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
X_1 R_1
X_2 R_2
\vdots
X_N R_N

Output

Output the maximum possible number of distinct coordinates where rabbits are present after jumping.

Sample Input 1

3
4 1
2 3
4 5

Sample Output 1

3

If each rabbit moves as shown below, it is possible to achieve 3 as the number of distinct coordinates where rabbits are present after jumping, and this is the maximum possible.

  • Rabbit 1 moves to 4 - 1 = 3.
  • Rabbit 2 moves to 2 + 3 = 5.
  • Rabbit 3 moves to 4 - 5 = -1.

Sample Input 2

6
2 1
3 2
6 1
5 2
4 3
4 1

Sample Output 2

4

If each rabbit moves as shown below, it is possible to achieve 4 as the number of distinct coordinates where rabbits are present after jumping, and this is the maximum possible.

  • Rabbit 1 moves to 2 - 1 = 1.
  • Rabbit 2 moves to 3 + 2 = 5.
  • Rabbit 3 moves to 6 + 1 = 7.
  • Rabbit 4 moves to 5 + 2 = 7.
  • Rabbit 5 moves to 4 - 3 = 1.
  • Rabbit 6 moves to 4 - 1 = 3.

Sample Input 3

10
1000000000 1000000000
1000000000 1
-1000000000 1000000000
-1000000000 1
0 1
2 1
1 2
4 1
3 2
4 3

Sample Output 3

9