Tram

Interview

Time limit1sMemory limit1024 MB

Summary

Choose the intercept a of the line y = x + a minimizing the sum of squared distances from given points to the line.

Level: Medium6 of 10
Topics: Math, Geometry, Binary search, Implementation
Solved: No attempts yet

Problem

It is 1815, and the politicians in Lund have just decided to build a tram line in Lund. Oh, sorry. That was wrong, let's start over. It is 2015, and the politicians in Lund have just decided to build a tram line in Lund.

The politicians have already decided that the tram line should run from south-east to north-west. To avoid too many complaints from the citizens, they want to make the line as useful as possible. Therefore they want to minimize the total unusefulness of the tram.

The unusefulness for citizen $i$ is equal to the square of the closest distance from the citizen's home to the tram line. The total unusefulness of the tram is the sum of all citizens' unusefulnesses.

Given the coordinates of each citizen's home, determine the value $a$ that minimizes the total unusefulness, where the equation of the tram line is $y=x+a$ .

Input

The first line of input contains an integer $1\leq N\leq 10^5$ , the number of citizens in Lund. Then follow $N$ lines, each with two space-separated integers $x\_i,y\_i$ ( $|x\_i|,|y\_i|\leq 10^6$ ), the coordinates of citizen $i$ 's home.

Output

Output a single number $a$ that minimizes the total unusefulness. An answer is accepted if its absolute or relative error is within $10^{-3}$ .

Examples3

Example 1
Input
```
3
1 1
2 2
3 3
```
Expected output
```
0.000000
```
Example 2
Input
```
3
0 1
1 0
1 1
```
Expected output
```
0.000000
```
Example 3
Input
```
3
0 2
1 1
1 0
```
Expected output
```
0.333333
```