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