Стас начал играть с круглыми ведерками в песочнице, раскидывая камешки, и его мама решила купить ему новое ведерко, а для этого ей надо решить следующую задачу:
Вам дано \(n\) различных точек с целочисленными координатами \(A_1, A_2, \ldots, A_n\). Все точки были сгенерированы из квадрата \([-10^8, 10^8] \times [-10^8, 10^8]\) равновероятно и независимо друг от друга.
Вам даны положительные целые числа \(k\), \(l\) такие, что \(k \leq l \leq n\). Вы хотите выбрать подотрезок \(A_i, A_{i+1}, \ldots, A_{i+l-1}\) массива точек (для некоторого \(1 \leq i \leq n + 1 - l\)), а затем окружность на плоскости, внутри или на границе которой лежит \(\geq k\) точек выбранного подотрезка.
Какой минимальный радиус может быть у такой окружности?
Выходные данные
Для каждого набора входных данных выведите единственное вещественное число — ответ на задачу.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит \(10^{-9}\). Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет зачтен, если \(\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}\).
Примечание
В первом наборе входных данных мы можем выбрать подотрезок \(A_1, A_2\) и окружность с центром \((0, 2)\) и радиусом \(2\).
Во втором наборе входных данных мы можем выбрать подотрезок \(A_1, A_2, A_3, A_4\) и окружность с центром \((1, 2)\) и радиусом \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 2 2
0 0
0 4
3 0
5 4 3
1 1
0 0
2 2
0 2
2 0
8 3 2
0 3
1 0
0 2
1 1
0 1
1 2
0 0
1 3
5 4 4
1 1
-3 3
2 2
5 3
5 5
|
2.00000000000000000000
1.00000000000000000000
0.50000000000000000000
4.00000000000000000000
|