Le Docteur peut aller où il veut. Néanmoins, il aime bien alterner les voyages courts et les voyages longs. C'est pourquoi il recherche ses destinations par paire. Une paire de destinations intéressantes contient deux destinations très proches, et il sera rapide et économique de passer de l'une à l'autre.
Le Tardis a pu fournir un ensemble de coordonnées pour 300 000 destinations disponibles dans un fichier zippé. Ce sont des coordonnées dans le plan (abscisse / ordonnée) qui reflètent la proximité des sites, selon une projection trop complexe à appréhender pour un Terrien comme vous. Mais bref... Si les points sont proches dans le plan, c'est qu'ils sont proches pour le Tardis.
Le jeu de coordonnées pourrait par exemple contenir (un point par ligne):
1, 0
2, -1
0, -2
-1, -2
-2, 0
-1, 2
Ce qui donne si on les dessine :
- La paire de points les plus proches est :
(-1, -2), (0, -2) - La deuxième paire de points les plus proches est :
(2, -1), (1, 0)
En entrée du problème, vous disposez des coordonnées des 300 000 points (voir plus haut). L'objectif est de trouver les 10 paires les plus proches.
Pour valider la réponse, il suffit de founir les coordonnées dans cet ordre : de la meilleure paire (celle qui contient les points les plus proches) à la moins bonne. Et pour chaque paire, on donnera en premier le point qui a la plus petite abcissse (et si les abscisses sont égales, on donnera en premier celui qui a la plus petite ordonnée).
Dans l'exemple précédent, on validerait en entrant :
-1, -2, 0, -2, 1, 0, 2, -1
Aidez le docteur à choisir ses 20 (10 paires) prochaines destinations. Vous aurez donc 40 nombres à donner.
