Балансировка нагрузки (Платина)
Балансировка нагрузки (Платина)
Коровы Фермера Джона стоят в различных точках (x1
, y1
) ... (xn
, yn
) его поля. ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением x = a (a - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением y = b, где b - чётное целое. Эти две изгороди пересекаются в точке (a, b) и вместе делят поле на четыре региона.
ФД хочет выбрать a и b так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть m - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы m было как можно меньше. Помогите ФД определить это минимально возможное значение для m.
Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 105
). Каждая из следующих n строк содержит местоположение одной коровы, указанное её координатами x и y (положительные нечётные целые числа, не превышающие 106
).
Выходные данные
Выведите минимально возможное значение m, которое может достичь ФД оптимальным расположением изгородей.
7 7 3 5 5 7 13 3 1 11 7 5 3 9 1
2