Ligne à haute tension

La conception des infrastructures d'une nouvelle ville à construire est en cours. Afin d'assurer un approvisionnement en électricité fluide et stable, il a été décidé de faire traverser la ville par une ligne à haute tension. Cependant, comme les lignes à haute tension induisent de puissants champs électromagnétiques, on souhaite les éloigner le plus possible des zones résidentielles.

Supposons que les zones résidentielles de la ville soient représentées par $N$ points sur un plan, et que la ligne à haute tension prenne la forme d'une ligne droite parfaite sur ce plan. Dans ce cas, la zone résidentielle la plus proche de la ligne à haute tension étant la plus affectée, la ligne à haute tension optimale doit traverser la ville tout en maximisant la distance minimale en ligne droite jusqu'à chaque point résidentiel. Traverser la ville signifie précisément qu'il existe au moins un point résidentiel de chaque côté de la ligne à haute tension (la droite).

Écrivez un programme qui calcule la configuration optimale de la ligne à haute tension et affiche la valeur minimale de la distance en ligne droite jusqu'à chaque point résidentiel dans ce cas.

Entrée

Les informations suivantes sont fournies sur l'entrée standard. La première ligne contient le nombre $N$ ($2 \le N \le 2,000$) de points résidentiels de la nouvelle ville. Chacune des $N$ lignes suivantes contient les coordonnées d'un point résidentiel sous la forme de deux entiers. Les coordonnées sont comprises entre $-10^9$ et $10^9$ inclus. Il n'existe pas deux points résidentiels ayant exactement les mêmes coordonnées dans l'entrée.

Sortie

Affichez sur la sortie standard, sous la forme d'un nombre réel, la distance minimale en ligne droite jusqu'à un point résidentiel pour la configuration optimale de la ligne à haute tension traversant la ville pour les points résidentiels donnés en entrée. La réponse sera considérée comme correcte si l'erreur absolue ou relative de la valeur réelle affichée est inférieure ou égale à $10^{-6}$. Pour rappel, l'erreur absolue correspond à |(valeur affichée) – (réponse correcte)|, et l'erreur relative correspond à |(valeur affichée) – (réponse correcte)| / (réponse correcte).

Sous-tâches

• Sous-tâche 1 : correspond à 14 points sur un total de 100 points, avec $N = 2$ ou $N = 3$.
• Sous-tâche 2 : correspond à 21 points sur un total de 100 points, avec $N \le 50$, et les coordonnées sont comprises entre –1 000 et 1 000 inclus. De plus, trois points résidentiels ne sont jamais alignés sur une même droite.
• Sous-tâche 3 : correspond à 9 points sur un total de 100 points, avec $N \le 500$, et les coordonnées sont comprises entre $-10^5$ et $10^5$ inclus. De plus, trois points résidentiels ne sont jamais alignés sur une même droite.
• Sous-tâche 4 : correspond à 30 points sur un total de 100 points, avec $N \le 2,000$, et les coordonnées sont comprises entre $-10^9$ et $10^9$ inclus. De plus, trois points résidentiels ne sont jamais alignés sur une même droite.
• Sous-tâche 5 : correspond à 26 points sur un total de 100 points, sans aucune contrainte supplémentaire au-delà des contraintes initiales.

Exemples

Entrée 1

4
0 0
1 1
0 1
1 0

Sortie 1

0.50000000

Entrée 2

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

Sortie 2

2.66789187