Optimize the Construction Process
You have been hired by a construction company to optimize the process of moving heavy construction materials from one place to another.
The construction field has a rectangular area with width
h. You can think of it as a rectangle that has the bottom left corner at the coordinate
(0, 0)and the top-right coordinate at
(w, h). The entrance is at the center of the bottom side of the construction site.
ncranes on the construction field at different locations
and each of them can transport a material if the material is within the reach of its jib. The cranes can rotate 360° and have a radius of reach
Given several destination points, the company would like to know the minimum number of cranes required that would get the materials from the entrance to that point.
The first line of the input contains two integers
h(2 ≤ w, h ≤ 200) where
The next line contains a single integer
n(1 ≤ n ≤ 50) representing the number of cranes.
nlines contain 3 integers
representing the coordinates of a crane and its radius of reach (0 ≤ ≤ w) (0 ≤ ≤ h) and (0 ≤ ≤ 200).
The following line contains a single integer
k(1 ≤ k ≤ 30) the number of destination points.
klines contain 2 integers
(0 ≤ ≤ w) (0 ≤ ≤ h) the destination coordinates.
The program should print
klines each one containing the minimum number of cranes required to reach the destination point. If it’s not possible to reach a destination point, the program should print
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
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB