Задача №1152. Информатизация садоводства
Дачный участок Степана Петровича имеет форму прямоугольника размером a × b. На участке имеется n построек, причем основание каждой постройки — прямоугольник со сторонами, параллельными сторонам участка.
Вдохновленный успехами соседей, Степан Петрович хочет посадить на своем участке m видов плодовых культур (участок Степана Петровича находится в северной местности, поэтому m = 1 или m = 2). Для каждого вида растений Степан Петрович хочет выделить отдельную прямоугольную грядку со сторонами, параллельными сторонам участка. Само собой, грядки не могут занимать территорию, занятую постройками или другими грядками.
Степан Петрович хочет расположить грядки таким образом, чтобы их суммарная площадь была максимальной. Грядки не должны пересекаться, но могут касаться друг друга.
| грядка №1 |
|
| |
| дом | |||
| сарай | грядка №2 | ||
|
| |||
Требуется написать программу, которая по заданным размерам участка и координатам построек определяет оптимальное расположение планируемых грядок.
В первой строке входного файла содержатся два целых числа n и m (0 ≤ n ≤ 10; 1 ≤ m ≤ 2).
Во второй строке содержатся два целых числа a и b (1 ≤ a, b ≤ 10000).
Далее следуют n строк, каждая из которых содержит четыре целых числа xi,1 , yi,1, xi,2, yi,2 –координаты двух противоположных углов постройки (0 xi,1 < xi,2 a, 0 yi,1 < yi,2 b). Различные постройки не могут пересекаться, но могут касаться друг друга.
В выходной файл необходимо вывести m строк, каждая из которых содержит координаты двух противоположных углов предполагаемой грядки. Координаты должны быть целыми (всегда можно добиться максимальной суммарной площади грядок, располагая их в прямоугольниках с целыми координатами).
В случае, если в вашем решении Степану Петровичу следует расположить менее m грядок, необходимо вывести для грядок, которые не следует сажать, строку «0 0 0 0» (см. второй пример ниже).
2 2 7 5 4 2 6 4 0 1 2 2
0 2 4 5 2 0 7 2
3 2 4 4 0 0 4 1 0 1 1 4 3 1 4 4
1 1 3 4 0 0 0 0