Задача №113176. Песочница
Прямоугольная детская площадка полностью замощена \(N\) плитками. Все плитки прямоугольные, возможно разного размера. Плитки не перекрываются.
На этой площадке решили построить песочницу. Чтобы подготовить место для песочницы, необходимо вынуть не более K плиток таким образом, чтобы песочница занимала все освободившееся пространство, была прямоугольной и имела максимально возможную площадь.
Напишите программу, которая определяет расположение песочницы, удовлетворяющей перечисленным выше требованиям.
Введем систему координат так, чтобы начало координат совпадало с одним из углов площадки, а оси координат шли вдоль сторон площадки. В этом случае противоположный угол площадки окажется в точке \((X,Y)\).
Первая строка содержит два числа \(X\) и \(Y\) (натуральные числа, не превышающие 10000). Во второй строке заданы числа \(N\) и \(K (1 \le K \le N \le 2000)\). Следующие \(N\) строк файла содержат по четыре целых числа \(X_{i,1}, Y_{i,1}, X_{i,2}, Y_{i,2}\), задающих координаты двух противоположных углов плитки.
Выведите координаты двух противоположных углов найденного прямоугольника. Если решений несколько, выведите любое из них.
В этой задаче 16 тестов, каждый тест оценивается независимо.
Гарантируется, что решения, корректно работающие при \(n \le 25\) наберут не менее 30 баллов.
Гарантируется, что решения, корректно работающие при \(n \le 500\) наберут не менее 42 баллов.
Гарантируется, что решения, корректно работающие при \(n \le 1500\) наберут не менее 54 баллов.
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