La tournée de Batman

C'est la panique à Gotham...

Dans sa Batcave, l'homme chauve-souris a installé du matériel très perfectionné afin de savoir où dans Gotham City, sont commis des délits. Il a ainsi un plan de toute la ville et les délits sont signalés directement sur le plan, la couleur indiquant le nom de son ennemi : Joker en rouge et Pinguin en bleu. La Batcave est symbolisée par un point vert. Les points de délits, ainsi que la Batcave, sont entourés d'un cercle jaune pour être plus facilement repérés :

Face à tous ces délits, et parce qu'il ne souhaite laisser de répit à aucun de ses ennemis, Batman va devoir se rendre alternativement sur un lieu de délit des hommes du Joker et sur un lieu de délit des hommes de Pinguin.

Sachant que le Batplane lui permet de se rendre en ligne droite à n'importe quel point de la ville, qu'il part de la Batcave (et qu'il devra y retourner), et qu'il alterne le traitement des incidents Joker et des incidents Pinguin (mais il peut commencer indifféremment par l'un ou par l'autre), quelle distance va-t-il parcourir au minimum ? Batman, soucieux des problèmes d'environnement, et parce que son véhicule volant consomme beaucoup d'énergie, veut en effet minimiser la longueur de son trajet. Pour résoudre le défi, vous devez donner cette longueur minimale en mètres (en arrondissant au mètre entier le plus proche), sachant qu'à l'échelle de la carte passer d'un pixel à un autre représente 2 mètres.

Exemple

Si le plan observé par Batman avait été le suivant :

Alors les positions suivantes des délits du Joker auraient été relevées :

    J1 = (12,12)
    J2 = (41,10)

ainsi que ceux de Pinguin :

    P1 = (47,29)
    P2 = (33,48)

La Batcave étant située en (28, 28), une meilleure tournée (son symétrique convient aussi) aurait été :

    Batcave - P2 - J2 - P1 - J1 - Batcave

La longueur de ce parcours en pixels aurait été 140.9... et avec l'échelle (1 pixel = 2m), la distance en mètres arrondie aurait été 282 m.

Ce problème est tiré de c0d1ng UP 2016

Type de retour

un nombre entier

Entrée du problème

Pas de donnée d'entrée

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup16 graphe combinatoire image