Африка на связи!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Mr. Beast решил наконец-то провести интернет в Африку. В Африке ровно $$$n$$$ населенных пунктов, имеющих координаты $$$(x_i, y_i)$$$, и Mr. Beast выбрал ровно $$$n$$$ подходящих гор с координатами $$$(x_j, y_j)$$$ и хочет распределить по одной на каждый населенный пункт. Чтобы жизнь малиной не казалась и скорости интернета в Африке хватало только на просмотр его видео, блогер хочет, чтобы минимальное расстояние от населенного пункта до горы, с ним соединенной, было максимальным. Сейчас Mr. Beast занят созданием нового ролика, поэтому он поручил вам составить оптимальный план соединения городов с горами по данным выше условиям.

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

В первой строке вводится натуральное число $$$n$$$ ($$$1 \le n \le 500$$$) — количество населенных пунктов и выбранных гор.

В следующих $$$n$$$ строках содержатся по $$$2$$$ числа $$$(x_i, y_i)$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — координаты населенных пунктов.

В следующих $$$n$$$ строках содержатся по $$$2$$$ числа $$$(x_j, y_j)$$$ ($$$-10^9 \le x_j, y_j \le 10^9$$$) — координаты гор.

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

Выведите одно число — максимальное минимальное расстояние от населенного пункта до соединенной с ним горы с точностью до $$$10^{-9}$$$.

Система оценки

Группы в данной задаче «склеиваются». Это означает, что за подгруппу начисляются баллы, если хотя бы одна из ваших посылок успешно проходит все её тесты.

Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи
$$$0$$$ | $$$0$$$ | Тесты из условия | —
$$$1$$$ | $$$15$$$ | $$$ n \leqslant 10$$$ | 0
$$$2$$$ | $$$15$$$ | $$$ y_i = y_j = 0$$$ | —
$$$3$$$ | $$$20$$$ | $$$ -10 \leqslant x_i, y_i, x_j, y_j \leqslant 10$$$ | 0
$$$4$$$ | $$$50$$$ | Нет дополнительных ограничений | 0, 1, 2, 3

Примеры

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

    21 12 23 34 4

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

    2.828427125

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

    5-1 21 35 1-2 12 -10 0-1 32 110 10-4 -3

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

    4.000000000