410167: GYM103967 C Защитное поле

C. Защитное полеограничение по времени на тест10 секундограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Рик и Морти ночуют на планете, на которой конкретно этой ночью температура достигнет абсолютного нуля. Оставшись без средств передвижения и без портальной пушки, они используют для выживания все, что могут, однако основной проблемой остается поиск пропитания.

К счастью, неподалеку от них находятся $$$n$$$ особей довольно вкусных обитателей данной планеты; $$$i$$$-я особь находится в точке с координатами $$$(x_i, y_i)$$$, если считать местность вокруг Рика и Морти приблизительно плоской. К сожалению, за ночь при абсолютном нуле эти существа замерзают на следующие несколько лет, поэтому Рик решил позаботиться о том, чтобы уберечь некоторую часть из них от холода и обеспечить себе и Морти питание на следующие дни. Для этого у Рика есть генератор защитного поля, которое не позволит температуре в некоторой круглой области опуститься так низко.

Центр защитного поля Рик может выбрать сам, но чтобы не тратить энергию попусту, он хочет установить защитное поле как можно меньшего радиуса. Однако Морти просит Рика уместить в защитном поле хотя бы $$$\left\lceil\frac{n}{2}\right\rceil$$$ особей, чтобы спасти их от вынужденной многолетней спячки.

Помогите Рику найти минимальный радус окружности, внутри которой содержится хотя бы половина существ-обитателей этой планеты.

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

В первой строке входных данных дано целое число $$$n$$$ — количество съедобных особей на планете ($$$1 \leqslant n \leqslant 400$$$).

В следующих $$$n$$$ строках даны $$$n$$$ пар вещественных чисел $$$x_i$$$ и $$$y_i$$$ — координаты местоположения каждой особи ($$$-{10}^9 \leqslant x_i, y_i \leqslant {10}^9$$$). Существа ленивые и никуда не двигаются, поэтому их положения постоянны.

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

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

ПримерыВходные данные

8
4 3
3 4
-3 4
-4 3
-4 -3
-3 -4
3 -4
4 -3

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

0 3 4

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

4
1.5 1.5
1.5 -1.5
-1.5 -1.5
-1.5 1.5

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

1.5 0 1.5