Wi-Fi – Qualification 2015

Level 5

Énoncé

Le maire de votre ville a eu une idée ambitieuse pour faire profiter à tous ses concitoyens d’Internet : installer un routeur Wi-Fi à chaque coin de rue. Tous les routeurs Wi-Fi ont toujours la même portée.

Pour le bien de la réélection du maire, celui-ci vous demande d’éviter de faire des jaloux : des concitoyens piégés dans une zone sans Wi-Fi isolée du reste du monde.

Vous pouvez fixer la portée minimale du routeur, sachant qu’elle peut être amenée à augmenter à différents moments de la journée. Ainsi, la portée réelle d’un routeur est toujours supérieure à la portée minimale.

Voici un exemple de différentes portées d’un routeur pour la configuration suivante. schema.png

Si quelle que soit la portée du routeur, il n’y a jamais de jaloux, renvoyez 0.

Entrée

L’entrée comprendra :

  • sur la première ligne, le nombre de points N ;
  • sur chacune des N lignes suivantes, deux coordonnées entières séparées par une espace : la i-ième ligne contiendra l’abscisse xi et l’ordonnée yi du i-ième hotspot wifi.

Sortie

Vous afficherez en sortie :

  • la portée minimale des routeurs Wi-Fi, avec une précision de 3 chiffres avec la virgule. On demande un arrondi et non une troncature, ansi si la réponse exacte commence par 0.04198... il faudra afficher 0.042.

Contraintes

  • 1 ≤ N ≤ 2000 ;
  • -10 000 ≤ xi, yi ≤ 10 000.

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
10000 milliseconds

Input/output samples

Sample input
3
0 0
1 1
2 2
Sample output
0
Sample input
4
0 0
0 2
2 2
2 0
Sample output
1.414

Submit your solution

You have to register or log in to be able to submit your solution.