Régate – Épreuve régionale 2014

Énoncé¶

Joseph Marchand est très embêté, il s'est vanté ouvertement de sa prochaine victoire au « tour du Pacifique à la voile », mais il avait juste trop bu, en fait, il n'est pas sûr du tout de gagner, pis, sans votre aide, il est sûr de perdre.

Les règles de la course sont les suivantes : - Les participants commencent la course sur l'île la plus à l'ouest de l'océan. - Ils ont 2 semaines pour passer par un ensemble d'îles donné et revenir à leur point de départ.

Les participants commencent sur l'île la plus à l'ouest car durant la première semaine de la course le vent vient de l'ouest, il leur est alors impossible de se déplacer contre le vent et doivent nécessairement aller vers une île à l'est de leur position courante. À la fin de la première semaine les temps sont enregistrés, tous les candidats attendent que le vent change de sens et ils repartent vers leur point de départ, en se déplaçant seulement vers l'ouest cette fois ci. Leur temps final est la somme du temps de la première semaine et de la deuxième semaine.

L'ordre dans lequel les îles doivent être visitées n'est pas donné, il n'est même pas dit si vous devez les visiter lors de la première ou de la seconde semaine.

C'est là que vous entrez en jeu, connaissant vos talents d'algorithmicien, Joseph vous demande de lui calculer la longueur du meilleur parcours, c'est à dire la longueur du plus court chemin passant par toutes les îles et revenant au point de départ en respectant les vents.

Peureusement, il vous demande d'arrondir le résultat vers le haut (au nombre entier supérieur ou égal le plus proche.)

Entrée¶

• Sur la première ligne, le nombre N d'îles.
• Sur les N lignes suivantes un couple d'entier x_i, y_i donnant la position de l'île numéro i.

Sortie¶

La longueur du plus court chemin passant par toutes les îles et retournant à l'île de départ en respectant les vents, arrondi par excès (à l'entier supérieur).

Contraintes¶

• 3 <= N <= 1 000
• 0 <= x_i, y_i <= 100 000