#P1446F. Line Distance
-
ID: 5668
Type: RemoteJudge
7000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Line Distance
No submission language available for this problem.
Description
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.
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.
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}$.
Input
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
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}$.
Samples
4 3
2 1
-2 -1
0 -1
-2 4
0.707106780737
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