Pluie de météorites – Épreuve régionale 2016

Énoncé¶

Un récursiraptor est pris au milieu d'une pluie de météorites.

Si une météorite lui tombe dessus, il meurt. Sinon il n'est pas touché, mais le tonnerre l'effraie et le récursiraptor va naturellement fuir dans la direction opposée. Une météorite laisse une zone incendiée à son point d'impact.

Le récursiraptor a si peur des impacts de météorites qu'il ne voit pas les incendies devant lui, et risque de se suicider en marchant dans le feu.

À partir des points d'impact successifs des météorites, déterminez le nombre de météorites auxquelles il survit.

Dans le schéma ci-dessous, le récursiraptor se trouve aux coordonnées initiales (x, y) = (2, 2). (0, 0) est le coin supérieur gauche (nord-ouest).

1
2
3
4
5

.....
.....
..R..
.....
.....

On distingue huit zones relatives à la position du récursiraptor :

• quatre demi-axes, nord N, est E, sud S, ouest O ;
• quatre quadrants, nord-ouest 1, nord-est 2, sud-est 3, sud-ouest 4.

1
2
3
4
5

11N22
11N22
OOREE
33S44
33S44

Une météorite tombe en (1, 0), dans le quadrant nord-ouest du dinosaure, qui s'éloigne en diagonale dans le quadrant opposé, vers le sud-est. La météorite laisse une zone incendiée.

1
2
3
4
5

.X...
.....
.....
...R.
.....

Une météorite tombe en (4, 3), juste à l'est du dinosaure, qui s'éloigne horizontalement dans la direction opposée, vers l'ouest.

1
2
3
4
5

.X...
.....
.....
..R.X
.....

Une météorite tombe en (2, 4), juste au sud du récursiraptor, qui s'éloigne verticalement dans la direction opposée, vers le nord.

1
2
3
4
5

.X...
.....
..R..
....X
..X..

Une météorite tombe, à nouveau, en (2, 4).

1
2
3
4
5

.X...
..R..
.....
....X
..X..

Une météorite tombe en (3, 4).

1
2
3
4
5

.#...
.....
.....
....X
..XX.

Le récursiraptor meurt brûlé.

Entrée¶

L'entrée comprendra :

• sur la première ligne, un entier n, le nombre d'impacts ;
• sur la seconde ligne, un couple d'entiers x et y séparés par une espace, la position initiale du dinosaure ;
• sur chacune des n lignes suivantes, deux entiers i, j séparés par des espaces, les points d'impact de météorites.

Sortie¶

La sortie est un unique entier : le nombre de météorites auquel il a survécu.

Contraintes¶

• 0 ≤ n ≤ 10 000
• 0 ≤ x, y, i, j ≤ 200