Задача №113445. Силовые поля
В физико-биологической лаборатории исследуют воздействие излучения на растения при облучении через силовые поля.
Экспериментальная установка содержит квадратную платформу размером \(10^9 \times 10^9\) , заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать \(n\) силовых полей.
Генератор силовых полей установлен над точкой (0, 0). При этом \(i\)-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и \((x_i , y_i)\).
В эксперименте планируется изучать воздействие излучения на растения при облучении через \(k\) силовых полей. Из заданных n полей необходимо выбрать \(k\) полей для эксперимента. Ученые хотят выбрать силовые поля таким образом, чтобы площадь участка платформы, над которой находятся все \(k\) выбранных силовых полей, была максимальна.
Требуется написать программу, которая по заданным целым числам \(n\), \(k\) и описанию \(n\) силовых полей определяет, какие \(k\) силовых полей необходимо выбрать для эксперимента, чтобы площадь участка, покрытого всеми \(k\) силовыми полями, была максимальна, и выводит площадь этого участка.
Первая строка входного файла содержит целые числа \(n\) и \(k\) (\(1 \le k \le n \le 200 000\)) — общее количество силовых полей и количество силовых полей, которые необходимо выбрать для эксперимента.
Последующие \(n\) строк содержат по два целых числа \(x_i , y_i (1 \le x_i , y_i \le 10^9\) ) — координаты дальнего от начала координат угла прямоугольного участка \(i\)-го силового поля.
Требуется вывести одно целое число: максимальную площадь искомого участка.
На рис. 1 показаны пять силовых полей, заданных во входном файле. Оптимальный способ выбрать из них три поля для эксперимента показан на рис. 2.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
5 3 3 5 2 2 2 5 4 4 5 3
9