Optimiser le processus de construction
Vous avez été embauché par une entreprise de construction pour rendre plus efficace le transport de matériaux lourds d’un endroit à un autre.
Le chantier prend la forme d’un rectangle de largeur
w et de hauteur h. Vous pouvez l’imaginer comme un rectangle dont le coin inférieur gauche se trouve à la position (0, 0) et dont le coin supérieur droit est à (w, h). L’entrée du site est située au centre du côté inférieur de ce terrain.Sur ce chantier, il y a
n grues placées à différents emplacements . Chacune de ces grues peut transporter un matériau se trouvant dans le rayon de sa flèche. Les grues peuvent pivoter à 360° et ont chacune un rayon d’action .Étant donné plusieurs points de destination, l’entreprise souhaite connaître le nombre minimum de grues nécessaires pour déplacer les matériaux depuis l’entrée jusqu’à chacun de ces points.
Entrée
La première ligne de l’entrée contient deux entiers
w et h (2 ≤ w, h ≤ 200) où w est pair.La ligne suivante contient un entier
n (1 ≤ n ≤ 50) correspondant au nombre de grues.Les
n lignes suivantes contiennent chacune 3 entiers qui indiquent les coordonnées d’une grue et le rayon de sa flèche (0 ≤ ≤ w) (0 ≤ ≤ h) et (0 ≤ ≤ 200).La ligne suivante contient un entier
k (1 ≤ k ≤ 30) représentant le nombre de points de destination.Les
k lignes qui suivent contiennent 2 entiers (0 ≤ ≤ w) (0 ≤ ≤ h) qui sont les coordonnées de chaque point de destination.Sortie
Le programme doit imprimer
k lignes, chacune indiquant le nombre minimum de grues nécessaires pour atteindre le point de destination. Si un point de destination ne peut pas être atteint, le programme doit afficher Impossible.Exemples
Entrée | Sortie |
4 4
2
2 1 1
2 3 1
5
2 2
3 2
1 2
2 3
3 3 | 1
Impossible
Impossible
2
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB