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