Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 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 |
|
|