CF1446F Line Distance

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} $ .

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 The third smallest distance among those is approximately $ 0.707106781 $ .