Line Distance
Contest: Codeforces Round 683 (Div. 1, by Meet IT)
Difficulty rating: 3200
Tags: binary search, data structures, geometry

You are given an integer $$$k$$$ and $$$n$$$ distinct points with integer coordinates on the Euclidean plane, the $$$i$$$-th point has coordinates $$$(x_i, y_i)$$$.

Consider a list of all the $$$\frac{n(n - 1)}{2}$$$ pairs of points $$$((x_i, y_i), (x_j, y_j))$$$ ($$$1 \le i < j \le n$$$). For every such pair, write out the distance from the line through these two points to the origin $$$(0, 0)$$$.

Your goal is to calculate the $$$k$$$-th smallest number among these distances.

Input format:
The first line contains two integers $$$n$$$, $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le \frac{n(n - 1)}{2}$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^4 \le x_i, y_i \le 10^4$$$)  — the coordinates of the $$$i$$$-th point. It is guaranteed that all given points are pairwise distinct.

Output format:
You should output one number — the $$$k$$$-th smallest distance from the origin. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

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

Note:
There are $$$6$$$ pairs of points:

- Line $$$1-2$$$ : distance $$$0$$$ from the origin
- Line $$$1-3$$$ : distance $$$\frac{\sqrt{2}}{2} \approx 0.707106781$$$ from the origin
- Line $$$1-4$$$ : distance $$$2$$$ from the origin
- Line $$$2-3$$$ : distance $$$1$$$ from the origin
- Line $$$2-4$$$ : distance $$$2$$$ from the origin
- Line $$$3-4$$$ : distance $$$\frac{2}{\sqrt{29}} \approx 0.371390676$$$ from the origin

Example input:
4 3
2 1
-2 -1
0 -1
-2 4

Example output:
0.707106780737

Editorial:
We can use binary search to solve the problem. Thus, it is sufficient for us to tell how many lines have distance from ($$$0$$$, $$$0$$$) larger than some given number $$$l$$$.
We need to find a way to think about the perpendicular distance, because it is impossible to draw all the $$$O(n^2)$$$ lines. The following simple lemma will be very helpful:
• Lemma 1. There are two points $$$A$$$, $$$B$$$ and an origin point $$$O$$$. If we draw two circles $$$o_A$$$, $$$o_B$$$ with centers $$$A$$$, $$$B$$$ and radii $$$AO$$$, $$$BO$$$ respectively, and denote by $$$X$$$ their second intersection point, then the length of $$$OX$$$ is twice the distance between line $$$AB$$$ and $$$O$$$.Proof This is due to the fact that triangles $$$AXB$$$ and $$$AOB$$$ are congruent.To be able to tell how many lines have distance from $$$O$$$ larger than $$$l$$$, we will consider $$$n$$$ circles - circle $$$o_i$$$ will have center ($$$x_i$$$, $$$y_i$$$) and pass through $$$O$$$. For every pair ($$$o_i$$$, $$$o_j$$$) we will define point $$$X_{ij}$$$ as above. We will also add a circle $$$o$$$ with center $$$O$$$ and radius $$$2l$$$. Now we want to know the number of points $$$X_{ij}$$$ which lie inside $$$o$$$. The other lemma will let us calculate this efficiently:
• Lemma 2. We will consider the same configuration as in lemma 1. and add a third cirle $$$o$$$ which intesects with $$$o_A$$$ at $$$A_1$$$, $$$A_2$$$ and with $$$o_B$$$ at $$$B_1$$$, $$$B_2$$$. Then the line segments $$$A_1A_2$$$ and $$$B_1B_2$$$ intersect if and only if $$$X$$$ doesn't lie inside $$$o$$$.Proof. This lemma is quite intuitive, if you imagine the red circle slowly expanding and look at the lines.It can be formally proved in the following way: consider geometric inversion with respect to circle $$$o$$$; line $$$A_1A_2$$$ would then be the image of $$$o_A$$$ and $$$B_1B_2$$$ would be the image of $$$o_B$$$. Hence the intersection $$$Y$$$ of these two lines is the image of "non-trivial" intersection of $$$o_A$$$ and $$$o_B$$$ - point $$$X$$$. $$$Y$$$ lies inside $$$o$$$ (in other words, $$$Y$$$ is the intersection of line segments $$$A_1A_2$$$, $$$B_1B_2$$$) if and only if $$$X$$$ is outside of it, which ends the proof.
For each $$$i$$$, we will draw a line segment between points of intersection of $$$o_i$$$ and $$$o$$$ (or do nothing if the circles don't intersect). Now our task is to calculate the number of pairs of line segments that intersect (this can be done in $$$O(n\log{n})$$$ time with use of a segment tree). Each intersecting pair will stand for one line with distance larger than $$$l$$$.

Precision issues while counting the number of intersections while checking some distance $$$l$$$ aren't a big problem, because they can only matter if we are very close to the true answer. Especially, it's important to notice that the segments $$$A_1A_2$$$, $$$B_1B_2$$$ touch at the endpoints exactly when the corresponding line's distance from the origin is $$$l$$$.
Total time complexity is $$$O(n \log{n})$$$ times around $$$35$$$ binsearch iterations needed for sufficient precision.