Après le déluge – Qualification 2016

Niveau 4

Énoncé

Grâce aux prévisions avérées du grand conseil des Prolosaures, un certain nombre de survivants au déluge ont pu se réfugier sur quelques îles émergées. Pour communiquer, un pacte a été conclu avec les Algoptéryx, dinosaures volants, grâce auxquels les bases de la communication ont pu s'établir entre les différentes îles. Malheureusement, ceux-ci commmencent à se lasser de leur rôle trop peu rémunérateur.

En guise de solution, le grand conseil des Prolosaures a imaginé déployer un grand réseau de téléphones yaourt entre les îles, grâce au concours des Algoptéryx.

Malheureusement, le fil nécessaire à leur confection se fait rare en ces temps post-apocalyptiques, et une récompense est prévue pour celui qui en minimisera l'usage.

Écrivez un programme qui permet de déterminer la longueur de fil minimale nécessaire pour rallier les différentes îles : toute île doit pouvoir communiquer, directement ou non, avec toutes les autres îles.

Entrées

L'entrée comprendra :

  • un entier naturel n représentant le nombre d'îles à rallier sur la première ligne ;
  • sur chacune des n lignes suivantes, les coordonnées entières relatives x et y d'une île, séparées par une espace.

Sortie

Vous afficherez en sortie :

  • un entier représentant la longueur de fil minimale nécessaire, arrondie à l'entier inférieur.

Contraintes

  • 1 ≤ n ≤ 1 000 ;
  • -10 000 ≤ xi, yi ≤ 10 000.

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
4
-1664 -2941
1969 -4009
7953 -5787
-1136 -1206
Exemple de sortie
11842
Exemple d'entrée
13
-2291 -71
-2784 -9693
-8879 4618
986 -8203
-4634 -1894
8827 -5805
7918 -2780
5618 -690
-7167 2618
437 -9308
-5573 9370
-3072 -3439
6832 -5064
Exemple de sortie
43897