Optimiza el proceso de construcción
Has sido contratado por una compañía constructora para optimizar el proceso de mover materiales de construcción pesados de un lugar a otro.
El campo de construcción tiene un área rectangular con ancho
w y alto h. Puedes pensarlo como un rectángulo que tiene su esquina inferior izquierda en la coordenada (0, 0) y la esquina superior derecha en (w, h). La entrada se encuentra en el centro del lado inferior del sitio de construcción.Existen
n grúas en el campo de construcción ubicadas en diferentes coordenadas , y cada una puede transportar un material si este se encuentra dentro del alcance de su brazo. Las grúas pueden rotar 360° y tienen un radio de alcance .Dado que hay varios puntos de destino, a la empresa le gustaría saber el número mínimo de grúas que se requieren para trasladar los materiales desde la entrada hasta ese punto.
Entrada
La primera línea de la entrada contiene dos enteros
w y h (2 ≤ w, h ≤ 200) donde w es par.La siguiente línea contiene un solo entero
n (1 ≤ n ≤ 50) que representa el número de grúas.Las siguientes
n líneas contienen 3 enteros que representan las coordenadas de una grúa y su radio de alcance (0 ≤ ≤ w) (0 ≤ ≤ h) y (0 ≤ ≤ 200).La siguiente línea contiene un solo entero
k (1 ≤ k ≤ 30), el número de puntos de destino.Las siguientes
k líneas contienen 2 enteros (0 ≤ ≤ w) (0 ≤ ≤ h), las coordenadas de destino.Salida
El programa debe imprimir
k líneas, cada una con el número mínimo de grúas requeridas para llegar al punto de destino. Si no es posible llegar a un punto de destino, se debe imprimir Impossible.Ejemplos
Entrada | Salida |
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