Pluie de météorites – Regional event 2016

Level 3

É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

Runtime constraints

Maximum memory usage
2000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

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

Le récursiraptor ne survit pas à la dernière météorite, qui l'envoie dans le feu.

Sample input
4
2 2
3 3
0 0
3 0
0 3
Sample output
4
Note

Le récursiraptor survit à toutes les météorites.

Sample input
1
42 42
42 42
Sample output
0
Note

Le récursiraptor se fait tuer immédiatement.

Submit your solution

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