Course baveuse – Épreuve régionale 2015

Énoncé¶

Joseph Marchand s'est récemment converti dans l'organisation de paris, mais pas n'importe lesquels. Il n'avait pas la place dans son salon pour faire courir des cheveaux, ni tout autre animal trop gros ou trop rapide. Après avoir demandé conseil autour de lui, c'est finalement dans son jardin qu'il a trouvé la solution : des courses d'escargots.

Cependant, ces courses sont particulières. Deux personnes apportent chacun n escargots, que l'on dispose au hasard sur une plaque en porcelaine carrée. Les escargots du premier joueur sont placés sur l'axe des ordonnées, et ceux du deuxième joueur sont placés sur l'axe des abscisses. Au top départ, les escargots avancent au maximum de leur vitesse en laissant une trainée derrière eux. Une traînée qui est plutôt dégoûtante, et qu'aucun escargot ne franchit : un escargot bloqué par la bave laissée par un escargot de l'autre joueur s'arrête et ne termine pas la course.

On vous fournit les coordonnées des 2N escargots, ainsi que la vitesse de chacun. Votre travail consiste à indiquer quel escargot gagne la course. Les escargots du premier joueur sont numérotés de 1 à N et ceux du deuxième joueur de N+1 à 2N. De plus, les positions et les vitesses sont des nombres entiers. On vous garantit que deux escargots ne passeront jamais par le même point en même temps. Les positions des escargots d'un même joueur sont triées.

Entrée¶

• Sur la première ligne, deux entiers : le nombre N d'escargots par joueur, ainsi que la taille c d'un côté de la plaque carrée.
• Sur les lignes 2, ..., N+1 : deux entiers par ligne : la position P_i et la vitesse V_i des escargots du premier joueur.
• Sur les lignes N+2, ..., 2N+1 : deux entiers par ligne : la position P_i et la vitesse V_i des escargots du deuxième joueur. Le point en bas à gauche est de coordonnées (0,0).

Sortie¶

Le numéro de l'escargot (en comptant ceux du joueur 1 en premier) qui va gagner la course.

Contraintes¶

• 0 < N ≤ 800
• 0 < c ≤ 1 000 000 000
• 0 < P₁ ≤ P₂ ≤ ... ≤ P_N < c
• 0 < P_N+1 ≤ P_N+2 ≤ ... ≤ P_2N < c
• 0 ≤ V_i ≤ 1 000 000 000