Оптимизация строительного процесса
Вас наняли в строительную компанию, чтобы оптимизировать процесс перемещения тяжелых строительных материалов с одного места на другое.
Строительная площадка представляет собой прямоугольную область шириной
w и высотой h. Можно представить её как прямоугольник с нижним левым углом в точке (0, 0) и верхним правым углом в точке (w, h). Вход на площадку расположен в центре нижней стороны этого прямоугольника.На строительной площадке установлено
n кранов, каждый из которых находится в координатах . Каждый кран может перемещать материал, если он находится в пределах досягаемости его стрелы. Краны могут поворачиваться на 360° и имеют радиус досягаемости .Для нескольких заданных конечных точек перед строительной компанией встала задача определить минимальное количество кранов, необходимых, чтобы переместить материалы от входа к каждой из этих точек.
Входные данные
В первой строке входных данных содержатся два целых числа
w и h (2 ≤ w, h ≤ 200), где w — чётное число.В следующей строке задаётся одно целое число
n (1 ≤ n ≤ 50), обозначающее количество кранов.В следующих
n строках содержатся 3 целых числа , задающие координаты крана и радиус его досягаемости (0 ≤ ≤ w), (0 ≤ ≤ h) и (0 ≤ ≤ 200).Далее идёт строка с одним целым числом
k (1 ≤ k ≤ 30), указывающим число конечных точек.В следующих
k строках содержатся по 2 целых числа , определяющих координаты конечных точек (0 ≤ ≤ w) (0 ≤ ≤ h).Выходные данные
Программа должна вывести
k строк, в каждой из которых указывается минимальное количество кранов, необходимых для достижения соответствующей конечной точки. Если добраться до конечной точки невозможно, программа должна вывести Impossible.Пример
Входные данные | Выходные данные |
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