Высоковольтная линия

В настоящее время ведётся проектирование инфраструктуры для строящегося нового города. Для обеспечения бесперебойного и стабильного электроснабжения было решено провести через город высоковольтную линию электропередач. Однако, поскольку высоковольтная линия создаёт мощное электромагнитное поле, желательно расположить её как можно дальше от жилых районов.

Представим жилые районы города в виде $N$ точек на плоскости, а высоковольтную линию — в виде бесконечной прямой на этой же плоскости. Поскольку жилой район, находящийся ближе всего к линии электропередач, подвергается наибольшему воздействию, оптимальная высоковольтная линия должна пересекать город так, чтобы максимизировать минимальное расстояние по прямой до любой из жилых точек. Тот факт, что высоковольтная линия (прямая) пересекает город, конкретно означает, что по обе стороны от линии находится хотя бы одна жилая точка.

Напишите программу, которая найдет оптимальное расположение высоковольтной линии и выведет минимальное расстояние по прямой от неё до жилых точек.

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

В первой строке входных данных содержится количество жилых точек нового города $N$ ($2 \le N \le 2,000$).

В следующих $N$ строках задаются координаты каждой жилой точки в виде двух целых чисел. Значения координат лежат в диапазоне от –$10^9$ до $10^9$ включительно. Никакие две заданные во входных данных жилые точки не имеют одинаковых координат.

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

Выведите вещественное число — минимальное расстояние по прямой от оптимальной высоковольтной линии, пересекающей город, до жилых точек.

Ответ считается правильным, если его абсолютная или относительная погрешность не превосходит $10^{-6}$. Напомним, что абсолютная погрешность равна |(выведенное значение) – (правильный ответ)|, а относительная погрешность равна |(выведенное значение) – (правильный ответ)| / (правильный ответ).

Подзадачи

• Подзадача 1: 14 баллов из 100, $N = 2$ или $N = 3$.
• Подзадача 2: 21 балл из 100, $N \le 50$, координаты лежат в диапазоне от –1 000 до 1 000. Никакие три жилые точки не лежат на одной прямой.
• Подзадача 3: 9 баллов из 100, $N \le 500$, координаты лежат в диапазоне от –$10^5$ до $10^5$. Никакие три жилые точки не лежат на одной прямой.
• Подзадача 4: 30 баллов из 100, $N \le 2,000$, координаты лежат в диапазоне от –$10^9$ до $10^9$. Никакие три жилые точки не лежат на одной прямой.
• Подзадача 5: 26 баллов из 100, дополнительных ограничений нет.

Примеры

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

4
0 0
1 1
0 1
1 0

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

0.50000000

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

10
-3 5
0 0
-1 6
0 8
8 2
4 0
7 -2
2 6
9 1
9 2

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

2.66789187