Problem Description

Mine clearance is a crucial and hazardous task on the battlefield. To address this, AL Military Factory has developed a specialized mine clearance robot designed for linear minefields. A linear minefield is one where all the mines are buried along a single straight line. For example, the black dots in the image represent a linear minefield.

The mine clearance robot produced by AL Military Factory uses only one method for clearing mines: safe detonation. Each time, the robot selects a mine from all detected mines to detonate. The detonated mine will trigger a chain reaction, causing other mines within its explosion radius to explode, which in turn may cause further chain reactions. For instance, in the image, the radius of the circle represents the explosion radius of the mine. If mine 2 is detonated, both mines 1 and 2 will explode; if mine 3 is detonated, all four mines will explode; and if mine 4 is detonated, only it will explode.

Although it is a robot, detonation is still dangerous. Therefore, the purchasers of the mine clearance robot hope that the robot can adopt a mine clearance strategy with the least number of detonations to destroy all mines in actual combat. Consequently, AL Military Factory intends to test the robot in this regard. To evaluate the robot's performance, AL Military Factory plans to calculate in advance the expected number of detonations required to complete the mine clearance task in a linear minefield (i.e., the input minefield) if detonations are performed randomly; and then compare this value with the robot's actual mine clearance strategy to assess its performance.

The term "random detonation" means that each time a mine is selected randomly with equal probability from all undetonated mines to detonate. After the chain reaction caused by this detonation ends, if there are still mines that have not been detonated, the above operation is repeated until all mines are detonated.

Input Format

The first line of input is a positive integer \( n \), representing the number of mines.

The next \( n \) lines describe each mine in the order of their positions. Each line contains two integers \( x_i \) and \( d_i \), which are the coordinates and the explosion radius of the mine, respectively. This means that the \( i \)-th mine can directly trigger the \( j \)-th mine if \( |x_i - x_j| \leq d \). The input guarantees: \( |x_i| \leq 10^8 \), \( 1 \leq d_i \leq 10^8 \).

Output Format

The output consists of a single line containing a real number, which is the answer. Round it to four decimal places.

Sample Input and Output

Sample Input #1

4
0 1
2 2
8 7
11 2

Sample Output #1

2.3333

Sample Input #2

3
-10 10
0 1
10 10

Sample Output #2

2.3333

Sample Input #3

2
1 10
2 100

Sample Output #3

1.0000

Sample Input #4

9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
1000 2000

Sample Output #4

1.8889

Notes/Hints

Hint

There are 10 additional input sample files robot20111.in~robot201110.in in the problem directory, along with their corresponding output sample files robot20111.out~robot201110.out. These data conform to all the specifications regarding data scale in this problem, but they are not the final test data.

Download Link, Password: ypbv.

Scoring Method

For each test case, if your output is \( YourAns \) and the standard answer is \( StdAns \), then:

• When \( |YourAns - StdAns| \leq 0.0001 \), you get 10 points for that test case.
• When \( 0.01 \geq |YourAns - StdAns| > 0.0001 \), you get 6 points for that test case.
• When \( 0.5 \geq |YourAns - StdAns| > 0.01 \), you get 2 points for that test case.
• Otherwise, you get 0 points for that test case.

Data Range

Test case 1: \( n \leq 20 \).

Test case 2: \( n \leq 200 \), and any strategy guarantees that the number of detonations does not exceed 20.

Test case 3: \( n \leq 200 \).

Test cases 4 to 5: \( n \leq 4000 \), and any strategy guarantees that the number of detonations does not exceed 20.

Test cases 6 to 10: \( n \leq 4000 \).

见题面 Input 部分

见题面 Output 部分