Площадь
Задачу добавил: alef
Успешно сдано решений: 0
Ночью на дороги города вышла и другая снегоуборочная техника. Однако нужно учесть, что на дорогах и тротуарах осталось много засыпанных снегом автомобилей, переместить которые куда-либо не представляется возможным. Много их оказалось и на центральной площади города. Водитель грейдера хочет знать, может ли он расчистить каким-либо образом дорогу, ведущую от одной стороны площади к другой, не задев при этом ни одного автомобиля.
Будем считать, что площадь может быть представлена в виде поля, разбитого на квадратные клетки. Каждый автомобиль может занимать прямоугольную область размером от одной до нескольких клеток. Грейдер занимает квадратную область, состоящую из одной или нескольких клеток. При движении он может разворачиваться на 90 градусов (и кратные 90 углы).
Формат входного файла input.txt
Первая строка – целые числа N (1 <= N <= 10000), M (1 <= M <= 10000), A (0 <= A <= 12) через пробел. N и M – ширина и длина площади (в клетках), A – количество автомобилей, оказавшихся на площади.
Вторая строка – целые числа XS, YS, XF, YF (1 <= XS, YS, XF, YF <= 10000) через пробел. XS, YS - координаты точки, возле которой находится грейдер перед началом движения, XF, YF – координаты точки, в которой грейдер должен оказаться (см. рис.)
Третья строка – целое число G (1 <= G <= 10) – размер стороны квадрата, обозначающего грейдер
Следующие A строк содержат информацию о засыпанных снегом автомобилях в формате
целые числа Xj, Yj, Wj, Hj через пробел (1 <= Xj, Yj <= 10000, 1 <= Wj, Hj <= 1000), Xj, Yj – координаты левого верхнего угла автомобиля #j, Wj и Hj (отсчитываются вправо и вниз от левого верхнего угла соответственно) - линейные размеры автомобиля
Формат выходного файла output.txt
Первая строка – целое число – минимально возможная площадь, которую нужно расчистить грейдеру, чтобы можно было проехать от одного конца площади до другого, или NO SOLUTION, если грейдер не сможет пройти через площадь, не задев ни одной машины.
Примечание. Грейдер чистит площадь, по которой прошел.
Пример входного файла
11 11 3
5 1 8 9
3
3 3 1 3
4 9 4 1
8 3 2 2
Пример выходного файла
42