Простая оболочка
Гари пытался создать простые ортогональные многоугольники для своей домашней работы по геометрии, но его алгоритм, похоже, имеет некоторые проблемы. После нескольких часов отладки он наконец понял, в чем проблема: очевидно, многоугольники, которые он генерировал, могут содержать самопересечения, что было совсем не тем, что он планировал!
В частности, “многоугольники“, созданные Гари, представлены списком n точек p[i]
= (x[i]
, y[i]
), образующих замкнутую многоугольную цепь. Многоугольная цепочка может содержать самопересечения. Сегменты, образованные каждыми двумя последовательными точками (x[i]
, y[i]
) и (x[j]
, y[j]
) в цепочке, являются либо вертикальными, либо горизонтальными.
Полигональные цепочки для тестовых примеров показаны ниже (не в масштабе):
Вы решили помочь Гари решить эту проблему, вычислив простой (не самопересекающийся) многоугольник с вертикальными и горизонтальными сегментами, который полностью содержит цепочку с как можно меньшей площадью. Какова площадь такого многоугольника?
Формально Вы должны вычислить нижнюю грань площадей всех простых ортогональных многоугольников, содержащих все отрезки [p[i]
, p[j]
] для каждых двух соседних точек p[i]
и p[j]
.
Giriş verilənləri
Первая строка содержит натуральное число n (4 ≤ n ≤ 100 000). Следующие n строк содержат точки (x[i]
, y[i]
) в порядке обхода многоугольника (1 ≤ x[i]
, y[i]
≤ 10^6
). Никакие две последовательные точки не совпадают, и нет двух последовательных вертикальных сегментов или двух последовательных горизонтальных сегментов.
Çıxış verilənləri
Выведите одно неотрицательное целое число - точную нижнюю грань площадей всех простых многоугольников, которые окружают замкнутую многоугольную цепочку. Можно доказать, что ответ всегда целочисленный.
Пример
В примерах 1 и 3 нет простых многоугольников с площадью в точности равной 50 и 8 соответственно; однако существуют простые многоугольники с площадями, произвольно близкими к этим значениям.