Apparitions divines – Épreuve régionale 2021

Énoncé¶

Dans l'ancien temps, les manifestations divines étaient prises très au sérieux.

Un réseau de tours d'observation avait été mis en place, et lorsqu'un dieu ou une déesse se manifestait un·e messager·e était alors immédiatement envoyé en partant de la tour d'observation la plus proche au temple du dieu ou de la déesse en question afin de les prévenir. Un·e scribe notait dans un registre alors la position de l'apparition ainsi que l'heure où le message était arrivé au temple.

Le temps a passé et aujourd'hui les archéologues ont récupéré tous les registres des apparitions de différents dieux et déesses, mais ils ont besoin de plus d'informations.

Les archéologues connaissent les positions des différents temples, les positions des différentes tours d'observations (on considère que les temples ne surveillent eux même les manifestations divines) et la vitesse des messagers.

Si une apparition se fait à équidistance de deux tours d'observations, la tour la plus proche du temple du dieu de l'apparition envoie un messager.

Les archéologues vous donnent ces informations, ainsi qu'une liste d'apparitions recensées dans différents temples, charge à vous de déterminer la date précise (à 2 secondes près) où l'apparition a été détectée à la tour d'observation.

On considère que dans l'ancien temps :

• 1 an = 12 mois
• 1 mois = 30 jours
• 1 jour = 24 heures
• 1 heure = 60 minutes
• 1 minute = 60 secondes

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : $v$, la vitesse du messager.
• Sur la ligne suivante, un entier : $t$, le nombre de temples.
• Sur les lignes suivantes, une liste de $t$ éléments : temple list, les temples.
  • Chaque élément de la liste est sur plusieurs lignes : une struct temple.
    • Sur la première ligne, une chaine de $255$ caractères : nom divinite, le nom de la divinité associée.
    • Sur la ligne suivante, une liste de $2$ entiers séparés par des espaces : position temple, la position du temple.
• Sur la ligne suivante, un entier : $n$, le nombre de tours d'observations.
• Sur les lignes suivantes, une liste de $t$ éléments : tour list, les positions des tours.
  • Une ligne par élément de la liste : une liste de $2$ entiers séparés par des espaces.
• Sur la ligne suivante, un entier : $m$, le nombre d'apparitions.
• Sur les lignes suivantes, une liste de $m$ éléments : apparition list, les apparitions.
  • Chaque élément de la liste est sur plusieurs lignes : une struct apparition.
    • Sur la première ligne, une chaine de $255$ caractères : nom apparition, nom de la divinité associée.
    • Sur la ligne suivante, une chaine de $100$ caractères : date time, date_time de la reception de l'apparition au temple.
    • Sur la ligne suivante, une liste de $2$ entiers séparés par des espaces : position apparition, la position de l'apparition.

Toutes les coordonnées sont données entières. Une unité sur le plan est égale à $100m$. Le format "date_heure" est le suivant : "jj-mm-aaaa_hh-mm-ss" (jour-mois-année_heure-minute-seconde).

Les années sont comptées de 0 à 9999, les mois de 00 à 11, les jours de 00 à 29, les heures de 00 à 11, les minutes et les secondes de 00 à 59.

Sortie¶

Pour chaque apparition, une ligne contenant la date et l'heure où elle a été aperçue en suivant le même format que pour l'entrée.

Contraintes¶

• $ 1 \leq t \leq 10^5$
• $ 1 \leq n \leq 10^5$
• $ 1 \leq m \leq 10^5$
• $ 1 \leq x, y \leq 10^5$
• Les apparitions se produisent de manière uniforme sur tout le territoire.
• Les tours d'observations sont globalement réparties de manière uniforme sur le territoire