Вам даны целое число \(k\) и \(n\) попарно различных точек с целочисленными координатами на евклидовой плоскости, \(i\)-я точка имеет координаты \((x_i, y_i)\).
Рассмотрим список всех \(\frac{n(n - 1)}{2}\) пар точек \(((x_i, y_i), (x_j, y_j))\) (\(1 \le i < j \le n\)). Для каждой такой пары выпишем расстояние от прямой, проходящей через эти две точки, до начала координат \((0, 0)\).
Ваша задача — вычислить \(k\)-е наименьшее число среди всех этих расстояний.
Выходные данные
Вы должны вывести одно число — \(k\)-е наименьшее расстояние до начала координат. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит \(10^{-6}\).
Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет зачтен, если и только если \(\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}\).
Примечание
Есть \(6\) пар точек:
- Прямая \(1-2\) : расстояние \(0\) от начала координат
- Прямая \(1-3\) : расстояние \(\frac{\sqrt{2}}{2} \approx 0.707106781\) от начала координат
- Прямая \(1-4\) : расстояние \(2\) от начала координат
- Прямая \(2-3\) : расстояние \(1\) от начала координат
- Прямая \(2-4\) : расстояние \(2\) от начала координат
- Прямая \(3-4\) : расстояние \(\frac{2}{\sqrt{29}} \approx 0.371390676\) от начала координат
Третье по возрастанию расстояние среди них составляет примерно
\(0.707106781\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
2 1
-2 -1
0 -1
-2 4
|
0.707106780737
|