F. Расстояние до прямой
ограничение по времени на тест
7.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны целое число $$$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$$$-е наименьшее число среди всех этих расстояний.

Входные данные

Первая строка содержит два целых числа $$$n$$$, $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le \frac{n(n - 1)}{2}$$$).

В $$$i$$$-й из следующих строк $$$n$$$ находятся два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$-10^4 \le x_i, y_i \le 10^4$$$) — координаты $$$i$$$-й точки. Гарантируется, что все заданные точки попарно различны.

Выходные данные

Вы должны вывести одно число — $$$k$$$-е наименьшее расстояние до начала координат. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-6}$$$.

Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Пример
Входные данные
4 3
2 1
-2 -1
0 -1
-2 4
Выходные данные
0.707106780737
Примечание

Есть $$$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$$$.