Blowing Candles

Time limit4sMemory limit512 MB

Summary

Given up to 200,000 points inside a disk, find the minimum width of a strip that can cover all of them.

Level: Hard8 of 10
Topics: Geometry, Brute force, Sorting, Divide and conquer
Solved: No attempts yet

Problem

Jacques-Édouard likes birthday cakes so much that he celebrates his birthday every hour instead of every year. His friends ordered a round cake from a famous pastry shop and placed candles on its top surface. The number of candles equals his age in hours, so a huge number of candles are burning on the cake. Jacques-Édouard wants to blow all of them out in one single breath.

Think of the flames as points in one plane, all inside a disk of radius $R$ nanometers centered at the origin. In that same plane, the air he blows travels along a straight strip of width $W$ , which is the region between two parallel lines at distance $W$ . Both lines belong to that region. Find the minimum width $W$ that lets him blow out every candle when he chooses the best orientation.

Input

The first line has the integers $N$ and $R$ , separated by a space, where $N$ is Jacques-Édouard's age in hours. Each of the next $N$ lines has the two integer coordinates $x_i$ and $y_i$ of the $i$ -th candle in nanometers, separated by a space.

Limits

$3 \le N \le 2 \times 10^5$
$10 \le R \le 2 \times 10^8$
$x_i^2 + y_i^2 \le R^2$ for every $i$ with $1 \le i \le N$
All points have distinct coordinates.

Output

Print $W$ on one line, rounded to exactly six digits after the decimal point. For example, print 20.000000 when the answer is $20$ .

Examples2

Example 1
Input
```
3 10
0 0
10 0
0 10
```
Expected output
```
7.071068
```

Example 2

Input

Expected output

20.000000