Задача 7. Силовые поля ≡
| Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
| Входной файл: | power.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | power.out | |||
| Максимальный балл: | 100 |
Условие
В физико-биологической лаборатории исследуют воздействие излучения на растения при облучении через силовые поля.
Экспериментальная установка содержит квадратную платформу размером 109 × 109, заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать n силовых полей.
Генератор силовых полей установлен над точкой (0, 0). При этом i-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и (xi, yi).
В эксперименте планируется изучать воздействие излучения на растения при облучении через k силовых полей. Из заданных n полей необходимо выбрать k полей для эксперимента. Ученые хотят выбрать силовые поля таким образом, чтобы площадь участка платформы, над которой находятся все k выбранных силовых полей, была максимальна.
Требуется написать программу, которая по заданным целым числам n, k и описанию n силовых полей определяет, какие k силовых полей необходимо выбрать для эксперимента, чтобы площадь участка, покрытого всеми k силовыми полями, была максимальна, и выводит площадь этого участка.
Формат входного файла
Первая строка входного файла содержит целые числа n и k — общее количество силовых полей и количество силовых полей, которые необходимо выбрать для эксперимента.
Последующие n строк содержат по два целых числа xi, yi — координаты дальнего от начала координат угла прямоугольного участка i-го силового поля.
Формат выходного файла
Требуется вывести одно целое число: максимальную площадь искомого участка.
Ограничения
1 ≤ k ≤ n ≤ 200 000, 1 ≤ xi, yi ≤ 109
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | |
|---|---|---|---|---|
| n | k | |||
| 1 | 18 | 1 ≤ n ≤ 20 | 1 ≤ k ≤ n | |
| 2 | 25 | 1 ≤ n ≤ 300 | 1 ≤ k ≤ n | 1 |
| 3 | 20 | 1 ≤ n ≤ 3000 | 1 ≤ k ≤ n | 1, 2 |
| 4 | 17 | 2 ≤ n ≤ 200 000 | k = 2 | |
| 5 | 20 | 1 ≤ n ≤ 200 000 | 1 ≤ k ≤ n | 1, 2, 3, 4 |
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Пояснение к примеру
На рис. 1 показаны пять силовых полей, заданных во входном файле. Оптимальный способ выбрать из них три поля для эксперимента показан на рис. 2.
Рис 1. Силовые поля в примере описания входных данных.
Рис 2. Оптимальный выбор трех из пяти силовых полей в данном примере.
Примеры тестов
| № | Входной файл (power.in) |
Выходной файл (power.out) |
|---|---|---|
| 1 | |
|