Силовые поля
(Время: 2 сек. Память: 64 Мб Сложность: 47%)
В физико-биологической лаборатории исследуют воздействие излучения на растения при облучении через силовые поля.
Экспериментальная установка содержит квадратную платформу размером 109 × 109, заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать n силовых полей.
Генератор силовых полей установлен над точкой (0, 0). При этом i-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и (xi , yi).
В эксперименте планируется изучать воздействие излучения на растения при облучении через k силовых полей. Из заданных n полей необходимо выбрать k полей для эксперимента. Ученые хотят выбрать силовые поля таким образом, чтобы площадь участка платформы, над которой находятся все k выбранных силовых полей, была максимальна.
Требуется написать программу, которая по заданным целым числам n, k и описанию n силовых полей определяет, какие k силовых полей необходимо выбрать для эксперимента, чтобы площадь участка, покрытого всеми k силовыми полями, была максимальна, и выводит площадь этого участка.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа n и k (1 ≤ k ≤ n ≤ 200 000) – общее количество силовых полей и количество силовых полей, которые необходимо выбрать для эксперимента.
Последующие n строк содержат по два целых числа xi , yi (1 ≤ xi, yi ≤ 109) – координаты дальнего от начала координат угла прямоугольного участка i-го силового поля.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число: максимальную площадь искомого участка.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 3
3 5
2 2
2 5
4 4
5 3 | 9 |
Пояснение к примеру
На рис. 1 показаны пять силовых полей, заданных во входном файле. Оптимальный способ выбрать из них три поля для эксперимента показан на рис. 2.
Рис 1. Силовые поля в примере описания входных данных.
Рис 2. Оптимальный выбор трех из пяти силовых полей в данном примере.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
