Ottimizzare il processo di costruzione
Sei stato assunto da un'azienda di costruzioni per rendere più efficiente il trasporto di materiali pesanti all’interno del cantiere, da un punto all’altro.
Il cantiere è costituito da un’area rettangolare con larghezza
w e altezza h. Puoi immaginarla come un rettangolo il cui angolo in basso a sinistra si trova nella coordinata (0, 0) e l’angolo in alto a destra si trova in (w, h). L’ingresso è situato al centro del lato inferiore dell’area di costruzione.All’interno del cantiere si trovano
n gru, posizionate in diversi punti ognuna delle quali può movimentare un carico se questo rientra nel raggio d’azione del suo braccio. Le gru possono ruotare di 360° e hanno un raggio di azione .Dato un insieme di punti di destinazione, l’azienda vuole determinare il numero minimo di gru necessario per spostare i materiali dall’ingresso fino a ciascun punto.
Input
La prima riga dell’input contiene due interi
w e h (2 ≤ w, h ≤ 200) dove w è pari.La riga successiva contiene un singolo intero
n (1 ≤ n ≤ 50) che rappresenta il numero di gru.Le successive
n righe contengono 3 interi che indicano le coordinate di ciascuna gru e il raggio del suo braccio (0 ≤ ≤ w) (0 ≤ ≤ h) e (0 ≤ ≤ 200).La riga seguente contiene un singolo intero
k (1 ≤ k ≤ 30), che specifica il numero di punti di destinazione.Le successive
k righe contengono 2 interi (0 ≤ ≤ w) (0 ≤ ≤ h) che rappresentano le coordinate di ogni punto di destinazione.Output
Il programma deve stampare
k righe, ognuna delle quali mostra il numero minimo di gru richiesto per raggiungere il punto di destinazione corrispondente. Se non è possibile raggiungere un determinato punto di destinazione, il programma deve stampare Impossible.Examples
Input | Output |
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