Armistice Area Apportionment
Contest: CROC 2016 - Elimination Round
Difficulty rating: 3200
Tags: binary search, geometry

After a drawn-out mooclear arms race, Farmer John and the Mischievous Mess Makers have finally agreed to establish peace. They plan to divide the territory of Bovinia with a line passing through at least two of the n outposts scattered throughout the land. These outposts, remnants of the conflict, are located at the points (x1, y1), (x2, y2), ..., (xn, yn).

In order to find the optimal dividing line, Farmer John and Elsie have plotted a map of Bovinia on the coordinate plane. Farmer John's farm and the Mischievous Mess Makers' base are located at the points P = (a, 0) and Q = ( - a, 0), respectively. Because they seek a lasting peace, Farmer John and Elsie would like to minimize the maximum difference between the distances from any point on the line to P and Q.

Formally, define the difference of a line $$e$$ relative to two points P and Q as the smallest real number d so that for all points X on line $$e$$, |PX - QX| ≤ d. (It is guaranteed that d exists and is unique.) They wish to find the line $$e$$ passing through two distinct outposts (xi, yi) and (xj, yj) such that the difference of $$e$$ relative to P and Q is minimized.

Input format:
The first line of the input contains two integers n and a (2 ≤ n ≤ 100 000, 1 ≤ a ≤ 10 000) — the number of outposts and the coordinates of the farm and the base, respectively.

The following n lines describe the locations of the outposts as pairs of integers (xi, yi) (|xi|, |yi| ≤ 10 000). These points are distinct from each other as well as from P and Q.

Output format:
Print a single real number—the difference of the optimal dividing line. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first sample case, the only possible line $$e$$ is y = x - 1. It can be shown that the point X which maximizes |PX - QX| is (13, 12), with $$| PX - QX | = | \sqrt { ( 1 3 - 5 ) ^ { 2 } + ( 1 2 - 0 ) ^ { 2 } } - \sqrt { ( 1 3 - ( - 5 ) ) ^ { 2 } + ( 1 2 - 0 ) ^ { 2 } } |$$, which is $$2\sqrt{13} \approx 7.211025509$$.

In the second sample case, if we pick the points (0, 1) and (0,  - 3), we get $$e$$ as x = 0. Because PX = QX on this line, the minimum possible difference is 0.

Example input:
2 5
1 0
2 1

Example output:
7.2111025509

Example input:
3 6
0 1
2 5
0 -3

Example output:
0.0000000000

Editorial:
We begin by binary searching on the the minimum possible difference. Thus we wish to solve the decision problem "Can a difference of k be achieved?" Consider the hyperbola |PX - QX| = k. Note that our answer is affirmative if and only if a pair of outposts defines a line that does not intersect the hyperbola.
Our next step is a reduction to an equivalent decision problem on a circle through a projective transformation. We express this transformation as the composition of two simpler operations. The first is an affine map that takes the hyperbola |PX - QX| = k to the unit hyperbola. The second maps homogenous coordinates (x, y, z) to (z, y, x). Under the latter, the unit hyperbola x2 - y2 = z2 goes to the unit circle x2 + y2 = z2.
Because projective transformations preserve collinearity, a line intersecting the hyperbola is equivalent to a line intersecting the circle. Thus we want to know if any pair of the outposts' images defines a line that does not intersect the circle. We now map the image of each outpost to the minor arc on the unit circle defined by its tangents. (We disregard any points lying inside the circle.) Observe that our condition is equivalent to the existence of two intersecting arcs, neither of which contains the other. Verifying that two such arcs exist can be done with a priority queue and a radial sweep line in $$O(n \log n)$$.
The total complexity of our solution is therefore $${\mathcal {O}}(n\log n\log P)$$, where P is the precision that we need.