Le marteau de Thor – Épreuve régionale 2024

Niveau 3 ⋅ Validation weight: 30%

Énoncé

Thor a laissé tomber son marteau, ce qui a brisé Midgard en plusieurs parties. Frigg, la déesse de l'amour, est très énervée après Thor car elle ne peut plus réunir des couples comme avant. Certains couples sont maintenant séparés par les brisures laissées par le marteau. Frigg aimerait savoir quels couples sont séparés, et pour cela elle demande à Jøsëf Marchand son aide.

Midgard est représenté par une grille de $\text{hauteur} \times \text{largeur}$ cases.

Les brisures sont représentées par une liste de paires d'entiers $\text{brisure x}, \text{brisure y}$.

Vous devez répondre à un nombre de requêtes de Frigg. Une requête contient deux positions où sont les deux personnes, premiere et seconde.

Pour chaque requête, répondez oui ou non selon s'il est possible que les deux personnes se rejoignent sans passer par les brisures. Les personnes peuvent uniquement se déplacer dans Midgard de case en case, vers la gauche, la droite, le haut ou le bas. Une personne ne peut donc pas avancer en diagonale.

La première case de la grille est à la position $(1, 1)$.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : largeur, la largeur de la grille représentant Midgard.
  • Sur la ligne suivante, un entier : hauteur, la hauteur de la grille représentant Midgard.
  • Sur la ligne suivante, un entier : nombre brisures, le nombre de brisures.
  • Sur les lignes suivantes, une liste de nombre brisures éléments : brisures, les positions de chaque brisure.
    • Une ligne par élément de la liste : séparés par des espaces, un entier brisure x (la colonne de la brisure), et un entier brisure y (la ligne de la brisure).
  • Sur la ligne suivante, un entier : nombre requetes, le nombre de requêtes.
  • Sur les lignes suivantes, une liste de nombre requetes éléments : requetes, la liste des requêtes.
    • Une ligne par élément de la liste : séparés par des espaces, un entier premiere x (colonne de la première personne), un entier premiere y (ligne de la première personne), un entier seconde x (colonne de la seconde personne), et un entier seconde y (ligne de la seconde personne).

Sortie

Pour chaque requête, indiquer sur une ligne si oui ou non le couple peut se rejoindre.

Contraintes

  • $1 \le largeur \le 1\,000$
  • $1 \le hauteur \le 1\,000$
  • $1 \le hauteur \times largeur \le 1\,000$
  • $1 \le nombre brisures \le 1\,000$
  • $1 \le nombre requetes \le 100$
  • $1 \le brisure x \le largeur$
  • $1 \le brisure y \le hauteur$
  • $1 \le premiere x \le largeur$
  • $1 \le premiere y \le hauteur$
  • $1 \le seconde x \le largeur$
  • $1 \le seconde y \le hauteur$

Contraintes de performance

  • $1 \le largeur \le 100\,000$
  • $1 \le hauteur \le 100\,000$
  • $1 \le hauteur \times largeur \le 100\,000$
  • $1 \le nombre brisures \le 100\,000$
  • $1 \le nombre requetes \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
2
3
2
1 2
2 3
5
1 1 2 1
1 1 2 2
1 1 1 3
2 1 1 3
2 1 2 1
Exemple de sortie
oui
oui
non
non
oui
Commentaire

Voici la grille de Midgard, où X représente une brisure :

midgard

  • La première requête concerne les deux positions au nord de Midgard. Ces deux positions étant adjacentes, les deux personnes peuvent se rejoindre facilement :

req1

  • La seconde requête concerne deux personnes un peu plus éloignées. Cependant, elles peuvent se retrouver en passant par la case au nord-est de Midgard :

req2

  • La troisième requête concerne deux personnes à l'ouest de Midgard. Cependant, ces deux personnes sont séparées par des brisures, et n'ont aucun moyen de se rejoindre sans passer par une brisure.

req3

  • La quatrième requête concerne deux personnes une nouvelle fois une personne bloquée au sud de Midgard. Encore une fois, cette personne ne peut pas retrouver l'autre personne au nord de Midgard, à cause des brisures.

req4

  • Enfin, la dernière requête concerne deux personnes se situant d'ores et déjà sur la même case. Elles n'ont donc aucun problème à se retrouver.

req5

Exemple d'entrée
1
10
3
1 2
1 6
1 8
4
1 1 1 3
1 3 1 4
1 3 1 5
1 4 1 10
Exemple de sortie
non
oui
oui
non
Commentaire

Voici la grille représentant l'état de Midgard :

midgard

  • Nous ne pouvons pas passer de 1 à 3, la réponse est non

req1

  • Nous pouvons passer de 3 à 4, la réponse est oui

req2

  • Nous pouvons passer de 3 à 5, la réponse est oui

req3

  • Nous ne pouvons pas passer de 4 à 10, la réponse est non

req4

Exemple d'entrée
4
4
4
1 2
2 2
3 2
4 3
3
1 1 1 4
1 4 4 4
1 1 4 4
Exemple de sortie
non
oui
non