Задача №112130. Песочница
Прямоугольная детская площадка полностью замощена N плитками. Все плитки прямоугольные, возможно разного размера. Плитки не перекрываются. На этой площадке решили построить песочницу. Чтобы подготовить место для песочницы, необходимо вынуть не более K плиток таким образом, чтобы песочница занимала все освободившееся пространство, была прямоугольной и имела максимально возможную площадь. Напишите программу, которая определяет расположение песочницы, удовлетворяющей перечисленным выше требованиям.
Введем систему координат так, чтобы начало координат совпадало с одним из углов площадки, а оси координат шли вдоль сторон площадки. В этом случае противоположный угол площадки окажется в точке ( X , Y ) . Первая строка входного файла содержит два числа X и Y (натуральные числа, не превышающие 10000 ). Во второй строке заданы числа N и K (1 ≤ K ≤ N ≤ 2000) . Следующие N строк файла содержат по четыре целых числа X i , 1 , Y i , 1 , X i , 2 , Y i , 2 , задающих координаты двух противоположных углов плитки (0 ≤ X i , 1 < X i , 2 ≤ X , 0 ≤ Y i , 1 < Y i , 2 ≤ Y ) .
В выходной файл выведите координаты двух противоположных углов найденного прямоугольника. Если решений несколько, выведите любое из них.
7 5 8 3 0 0 2 1 2 0 4 1 0 1 1 3 1 1 4 3 0 3 4 4 0 4 6 5 4 0 6 4 6 0 7 5
0 1 4 4