Après le déluge – Qualification 2016

É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 ≤ x_i, y_i ≤ 10 000.