Otimize o Processo de Construção
Foi contratado por uma empresa de construção para otimizar o processo de transporte de materiais de construção pesados de um local para outro.
O campo de construção tem uma área retangular com largura
w e altura h. Pode imaginá-lo como um retângulo que tem o canto inferior esquerdo na coordenada (0, 0) e o canto superior direito na coordenada (w, h). A entrada do local de construção encontra-se no centro do lado inferior do terreno.Existem
n guindastes no campo de construção, cada um posicionado em diferentes locais . Todos eles podem transportar um material, desde que o material esteja dentro do raio de alcance de suas lanças. Os guindastes conseguem girar 360° e têm raios de alcance .Diante de vários pontos de destino, a empresa gostaria de saber qual o número mínimo de guindastes necessário para levar o material desde a entrada até cada um desses pontos.
Entrada
A primeira linha da entrada contém dois inteiros
w e h (2 ≤ w, h ≤ 200) onde w é par.A linha seguinte contém um único inteiro
n (1 ≤ n ≤ 50), que representa o número de guindastes.Nas próximas
n linhas, são fornecidos 3 inteiros , que indicam as coordenadas de um guindaste e o seu raio de alcance (0 ≤ ≤ w), (0 ≤ ≤ h) e (0 ≤ ≤ 200).Na próxima linha aparece um único inteiro
k (1 ≤ k ≤ 30), que é o número de pontos de destino.Nas próximas
k linhas, são fornecidos 2 inteiros (0 ≤ ≤ w) (0 ≤ ≤ h), que são as coordenadas de cada ponto de destino.Saída
O programa deve imprimir
k linhas, cada uma contendo o número mínimo de guindastes necessário para alcançar o ponto de destino correspondente. Caso não seja possível alcançar determinado ponto, o programa deve imprimir Impossible.Exemplos
Entrada | Saída |
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