Línea de alta tensión

El diseño de la infraestructura para una nueva ciudad que se va a construir está en marcha. Para garantizar un suministro de energía fluido y estable, se ha decidido que una línea de alta tensión cruce esta ciudad. Sin embargo, dado que las líneas de alta tensión inducen un fuerte campo electromagnético, se desea mantener la mayor distancia posible de las zonas residenciales.

Representemos las zonas residenciales de la ciudad como $N$ puntos en un plano, y supongamos que la línea de alta tensión tiene la forma de una línea recta perfecta en este plano. En este caso, dado que el punto residencial más cercano a la línea de alta tensión será el más afectado, la línea de alta tensión óptima debe cruzar la ciudad maximizando el valor mínimo de la distancia en línea recta hasta cada punto residencial. Que la línea de alta tensión (línea recta) cruce la ciudad significa específicamente que existe al menos un punto residencial a ambos lados de la línea de alta tensión.

Escriba un programa que calcule la forma de la línea de alta tensión óptima e imprima la distancia mínima en línea recta hasta cada punto residencial en dicho caso.

Entrada

Se proporciona la siguiente información a través de la entrada estándar. En la primera línea se proporciona la cantidad de puntos residenciales de la nueva ciudad, $N$ ($2 \le N \le 2,000$), y en las siguientes $N$ líneas se proporcionan las coordenadas de cada punto residencial mediante dos números enteros. El rango de las coordenadas es mayor o igual a –$10^9$ y menor o igual a $10^9$. En ningún caso dos puntos residenciales dados en la entrada tendrán exactamente las mismas coordenadas.

Salida

Imprima en la salida estándar, como un número real, el valor mínimo de la distancia en línea recta hasta los puntos residenciales para la forma óptima de la línea de alta tensión que cruza la ciudad dada en la entrada. Se considerará correcta la respuesta si el error absoluto o el error relativo del valor real impreso es menor o igual a $10^{-6}$. Como referencia, el error absoluto representa |(valor impreso) – (respuesta correcta)|, y el error relativo representa |(valor impreso) – (respuesta correcta)| / (respuesta correcta).

Subtareas

• Subtarea 1: Corresponde a 14 de los 100 puntos totales, y $N = 2$ o $N = 3$.
• Subtarea 2: Corresponde a 21 de los 100 puntos totales, $N \le 50$, y el rango de las coordenadas es mayor o igual a –1,000 y menor o igual a 1,000. Además, en ningún caso tres puntos residenciales se encuentran sobre una misma línea recta.
• Subtarea 3: Corresponde a 9 de los 100 puntos totales, $N \le 500$, y el rango de las coordenadas es mayor o igual a –$10^5$ y menor o igual a $10^5$. Además, en ningún caso tres puntos residenciales se encuentran sobre una misma línea recta.
• Subtarea 4: Corresponde a 30 de los 100 puntos totales, $N \le 2,000$, y el rango de las coordenadas es mayor o igual a –$10^9$ y menor o igual a $10^9$. Además, en ningún caso tres puntos residenciales se encuentran sobre una misma línea recta.
• Subtarea 5: Corresponde a 26 de los 100 puntos totales y no tiene ninguna restricción adicional aparte de las restricciones originales.

Ejemplos

Entrada 1

4
0 0
1 1
0 1
1 0

Salida 1

0.50000000

Entrada 2

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

Salida 2

2.66789187