Rond-point – Qualification 2015

Level 3

É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 X1, Y1 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 Xi, Yi 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.

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
500 milliseconds

Input/output samples

Sample input
1 1
4
1 0
1 2
0 1
2 1
Sample output
2 1
Note

schema.png

Sample input
1 1
3
1 0
0 0
2 1
Sample output
2 1

Submit your solution

You have to register or log in to be able to submit your solution.