Rond-point – Qualification 2015

Énoncé¶

La voiture de Joseph Marchand a un problème technique : son clignotant droit fonctionne en permanence, impossible de l’arrêter. Voulant respecter le code de la route, il décide de toujours prendre la première à droite.

Étant équipé d’un modèle de voiture dernier cri avec un assistant de navigation intégré, Joseph Marchand vous demande d’écrire une application qui lui dit quelle direction prendre lorsqu’il arrive sur un rond-point.

On vous donne les coordonnées du rond-point, et une liste de coordonnées représentant les différentes destinations des sorties du rond-point. La voiture arrive sur le rond-point depuis la première de ces destinations dans la liste. Écrivez une fonction qui renvoie les coordonnées de la destination de la sortie qui correspond, du point de vue de Joseph Marchand, à la première sortie du rond-point.

Entrée¶

L’entrée comprendra :

• sur la première ligne, les coordonnées X, Y du rond-point, séparées d’une espace ;
• sur la deuxième ligne, le nombre N de sorties du rond-point ;
• sur la troisième ligne, les coordonnées X₁, Y₁ du bout de la route par laquelle arrive la voiture, séparées d’une espace ;
• sur les N - 1 lignes suivantes, les coordonnées X_i, Y_i des destinations de chacune des sorties, séparées d’une espace.

Sortie¶

Vous afficherez en sortie :

• les coordonnées de la destination de la sortie correspondant à la première sortie du rond-point.

Contraintes¶

• 2 ≤ N ≤ 10 001 ;
• chaque coordonnée est entière et comprise entre -10 000 et 10 000 ;
• les coordonnées mènent toutes vers des directions différentes : les routes (segments de droite allant du rond-point jusqu’à leurs destinations) ne se chevauchent pas.