F. Накрывающая окружность
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Стас начал играть с круглыми ведерками в песочнице, раскидывая камешки, и его мама решила купить ему новое ведерко, а для этого ей надо решить следующую задачу:

Вам дано $$$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$$$ точек выбранного подотрезка.

Какой минимальный радиус может быть у такой окружности?

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке описания каждого набора входных данных находится три целых числа $$$n$$$, $$$l$$$, $$$k$$$ ($$$2 \leq k \leq l \leq n \leq 50\,000$$$, $$$k \leq 20$$$).

В каждой из следующих $$$n$$$ строк написано два целых числа $$$x_i$$$, $$$y_i$$$ ($$$-10^8 \leq x_i, y_i \leq 10^8$$$) — координаты точки $$$A_i$$$. Гарантируется, что все точки различны и были сгенерированы из квадрата $$$[-10^8, 10^8] \times [-10^8, 10^8]$$$ равновероятно и независимо друг от друга.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$50\,000$$$.

В первом тесте точки не были сгенерированы из равномерного распределения в квадрате $$$[-10^8, 10^8] \times [-10^8, 10^8]$$$ для простоты. Это единственный такой тест и ваша программа должна его проходить.

Взломы в задаче запрещены.

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

Для каждого набора входных данных выведите единственное вещественное число — ответ на задачу.

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

Пример
Входные данные
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
Примечание

В первом наборе входных данных мы можем выбрать подотрезок $$$A_1, A_2$$$ и окружность с центром $$$(0, 2)$$$ и радиусом $$$2$$$.

Во втором наборе входных данных мы можем выбрать подотрезок $$$A_1, A_2, A_3, A_4$$$ и окружность с центром $$$(1, 2)$$$ и радиусом $$$1$$$.