Partie de Cache Cache – Qualification 2026

Niveau 4 ⋅ Validation weight: 15%

Énoncé

Joseph souhaite jouer à cache-cache avec son ami robot Rob1DesBois. Pour cela, ils décident d'aller tous ensemble jouer au parc. Après avoir compté jusqu'à 30, Joseph rouvre les yeux et remarque directement certains robots mal cachés.

Le parc a une forme de rectangle et a pour dimension $L$ par $H$. Le parc a été conçu avec des blocs de jeu en forme de cube de côté de taille $1$, utilisés comme murs.

Vous aurez à répondre à $R$ requêtes. Pour chaque requête, on vous indique la position ($x, y$) du robot. Vous devrez alors déterminer si le robot est visible du point de vue de Joseph.

On considère Joseph et le robot comme des points se situant au centre de leur case. On considère que le robot est visible si le segment allant de Joseph au robot n'intersecte aucun mur ni coin de mur.

Pour chaque requête, affichez VISIBLE si Joseph peut voir le robot, ou CACHE si Joseph ne peut pas le voir.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : L, la largeur de la carte.
  • Sur la ligne suivante, un entier : H, la hauteur de la carte.
  • Sur la ligne suivante, séparés par des espaces, un entier x (la coordonnée X), et un entier y (la coordonnée Y) : joseph, la position de Joseph.
  • Sur la ligne suivante, un entier : M, le nombre de murs.
  • Sur les lignes suivantes, une liste de M éléments : murs, la position de chaque mur.
    • Une ligne par élément de la liste : séparés par des espaces, un entier x (la coordonnée X), et un entier y (la coordonnée Y).
  • Sur la ligne suivante, un entier : R, le nombre de requêtes.
  • Sur les lignes suivantes, une liste de R éléments : requetes, pour chaque requête, la position du robot.
    • Une ligne par élément de la liste : séparés par des espaces, un entier x (la coordonnée X), et un entier y (la coordonnée Y).

Sortie

Pour chaque requête, dans l'ordre, afficher VISIBLE si le robot est visible par Joseph, CACHE sinon.

Contraintes

  • $1 \le L, H \le 50$
  • $1 \le M, R \le 100$
  • $1 \le x \le L$
  • $1 \le y \le H$
  • Toutes les requêtes sont distinctes, tous les murs sont distincts, et aucune requête ni Joseph ne se situe dans un mur

Contraintes de performance

  • $1 \le L, H \le 100\,000$
  • $1 \le M, R \le 100\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6
3
1 3
3
3 2
4 2
5 2
2
1 1
5 1
Exemple de sortie
VISIBLE
CACHE
Commentaire

Ici Joseph ne peut voir qu'un robot : le premier. Le second est caché par les murs.

sample

En bleu, la position de Joseph. En noir, les deux positions évoquées pour le robot.

Exemple d'entrée
4
3
1 3
2
2 2
3 2
5
1 1
2 1
4 1
4 2
4 3
Exemple de sortie
VISIBLE
CACHE
CACHE
CACHE
VISIBLE
Commentaire

Seuls le premier et le dernier robot sont visibles.

Exemple d'entrée
2
4
1 1
1
2 2
3
1 3
1 4
2 4
Exemple de sortie
VISIBLE
VISIBLE
CACHE
Commentaire

Les 2 robots de gauches sont visibles mais celui de droite est caché.