\(N\) коров (\(3 \leq N \leq 50,000\)) фермера Джона размещены в различных
позициях его двумерного поля. ФД хочет огородить всех коров прямоугольным
забором, стороны которого параллельны осям координат x и y. ФД хочет, чтобы
забор был как можно меньше, и содержал всех коров (допускается размещение
коров на границе забора).
К несчастью бюджет ФД ограничен, поэтому он решил построить ещё меньший забор,
продав одну корову.
Помогите ФД вычислить наименьшую возможную площадь, которую он может огородить,
забором после удаления одной коровы из стада и огораживания оставшихся \(N-1\)
коров.
Для этой задачи рассматриваем коровы как точки, а забор как коллекцию
из четырёх отрезков прямых. (То есть не думайте о корове как единичном квадрате).
Заметим, что ответ может быть равным 0, например, если оставшиеся коровы все стоят
на одной вертикальной или горизонтальной прямой. Наконец, поскольку \(N\)
может быть довольно большим, Вы должны написать программу, которая будет
работать достаточно быстро.
ФОРМАТ ВВОДА (файл reduce.in):
Первая строка ввода содержит \(N\). Каждая их следующих \(N\) строк содержит
два целых числа, указывающих координаты коровы. Координаты - положительные
целые числа в интервале \(1 \ldots 40,000\).
ФОРМАТ ВЫВОДА (файл reduce.out):
Выведите целое число, указывающее минимальную площадь, которую огородит
своим забором ФД после удаления правильно выбранной коровы.
Ваш ответ: