D - Snowballs Editorial /

Time Limit: 1 sec / Memory Limit: 976 MB

配点：600 点

問題文

西から東に延びる十分に長い一直線の道路があります。道路には N 個の雪玉があります。
道路上で「X の位置」とは、ある道路上の地点を基準として距離 X だけ東に進んだ位置という意味です。

i 個目の雪玉は、道路の西端から X_i の位置にあり、半径は R_i です。すべての雪玉は球体であると仮定してもよいです。

E869120 君は、雪玉を合体させてできるだけ大きい雪玉を作ろうと考えました。

雪玉を距離 d 動かすと、半径は d 小さくなります。半径が 0 になると、雪玉は消滅します。
また、同じ座標にある雪玉を合体させることもできます。半径 r_1 の雪玉と半径 r_2 の雪玉を合体させると、半径 \left(r_1^3 + r_2^3\right)^{1/3} の雪玉になる。

さて、E869120 君が作れる最大の雪玉の半径はいくつでしょうか？

制約

  • 1 \leq N \leq 100 \ 000
  • 1 \leq X_i \leq 1 \ 000 \ 000 \ 000
  • 1 \leq R_i \leq 1 \ 000 \ 000 \ 000

小課題・得点

この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。

  1. (70 点)：N = 2
  2. (140 点)：N \leq 15
  3. (250 点)：N \leq 1 \ 000
  4. (140 点)：追加の制約はない。

入力

入力は以下の形式で標準入力から与えられます。 

N
X_1 R_1
X_2 R_2
 :  :
X_N R_N

出力

E869120 君が作れる最大の雪玉の半径を 1 行で出力してください。
ただし、相対誤差または絶対誤差が 10^{-4} 以内の場合、正答とみなされる。

入力例 1

2
4 5
7 9

出力例 1

9.03280211228081065

次のような操作をすると、半径 737^{1/3} = 9.03280... の雪玉を作ることができます。

  • 1 個目の雪玉を、距離 3 だけ東に移動させます。すると、半径が 3 減って 2 になります。
  • 1 個目の雪玉と 2 個目の雪玉を合体させます。合体後の半径は \left(9^3 + 2^3\right)^{1/3} = 9.03280... になります。

これが作れる最大の雪玉の半径になります。

入力例 2

5
3 4
1 4
1 2
9 10
5 3

出力例 2

9.99999999999999645

4 個目の雪玉は最初から半径 10 ですが、このケースではこれ以上の大きさの雪玉をどうやっても作ることができません。
また、誤差が 10^{-4} まで認められるので (「出力」セクション参照)、例えば 9.9992 や 10.000869120 などの出力をしてもよいです。

入力例 3

9
815886884 307027576
432574413 156832535
869389414 537542354
8271358 844638329
34762585 93905560
445922147 508315922
476305579 724641385
15004200 341668840
277786703 825590503

出力例 3

1000677079.68994784

半径・位置の制約が 10^9 以下であるとはいえ、答えが 10^9 を超える場合があります。

Max Score：600 points

Problem Statement

There is a very long straight road, from west to east. The road can be expressed as number line, which west is negative direction and east is positive direction.

There are N snowballs in the road. The i-th snowballs is at coordinate X_i and the radius is R_i. We can assume that shape of all snowballs are spheres.

E869120 is trying to make the largest possible snowballs by combining some of them.

When he moves a snowball by distance d, the radius of it will be decreased by d. When the radius becomes zero, the snowball disappears.
Also, he can combine two snowballs at the same coordinates. When he combines snowballs of radius r_1 and r_2, the radius of the combined snowball will be \left(r_1^3 + r_2^3\right)^{1/3}.

Calculate the maximum possible radius E869120 can make, please!

Constraints

  • 1 \leq N \leq 100 \ 000
  • 1 \leq X_i \leq 1 \ 000 \ 000 \ 000
  • 1 \leq R_i \leq 1 \ 000 \ 000 \ 000

Subtasks / Scoring

This problem is separated several two subtasks, and you will get score of the subtask if your program prints the correct answer for all testcases for the subtask prepared.
The score for a program is the sum of score of subtasks of correct answer.

  1. (70 points)：N = 2
  2. (140 points)：N \leq 15
  3. (250 points)：N \leq 1 \ 000
  4. (140 points)：No additional constraints.

Input

The input will be given from standard input, in the following format. 

N
X_1 R_1
X_2 R_2
 :  :
X_N R_N

Output

Print the maximum possible radius E869120 can make.
Since it will be a real number, your solution will be correct if the absolute or relative error does not exceed 10^{-4}.

Sample Input 1

2
4 5
7 9

Sample Output 1

9.03280211228081065

If E869120 does the following operation, he can obtain a snowball of radius 737^{1/3} = 9.03280....

  • Move 1-st snowball to the east by distance 3. Then, the radius will be decreased by 3 and become 2.
  • Combine 1-st and 2-nd snowballs. The radius after combining will be \left(9^3 + 2^3\right)^{1/3} = 9.03280....

And this is the largest possible snowball he can make.

Sample Input 2

5
3 4
1 4
1 2
9 10
5 3

Sample Output 2

9.99999999999999645

4-th snowball has radius of 10 initially, but he cannot obtain the snowball larger than that, in this case.
In addition, this problem admits error less than 10^{-4} (see "Output" section for details), so printing like 9.9992 or `10.000869120' will also be correct.

Sample Input 3

9
815886884 307027576
432574413 156832535
869389414 537542354
8271358 844638329
34762585 93905560
445922147 508315922
476305579 724641385
15004200 341668840
277786703 825590503

Sample Output 3

1000677079.68994784

Although the radius and coordinate is 10^9 or less, the answer may exceed 10^9.