Проста оболонка
Гаррі намагався створити прості ортогональні багатокутники для своєї домашньої роботи з геометрії, але його алгоритм, схоже, має деякі проблеми. Після кількох годин налагодження він нарешті зрозумів, у чому проблема: багатокутники, які він генерував, можуть містити самоперетини, що зовсім не входило в його плани!
Зокрема, “багатокутники“, створені Гаррі, представлені списком n точок p[i] = (x[i], y[i]), що утворюють замкнений багатокутний рядок. Цей рядок може містити самоперетини. Сегменти, утворені кожними двома послідовними точками (x[i], y[i]) і (x[j], y[j]) у рядку, є або вертикальними, або горизонтальними.
Полігональні рядки для тестових прикладів показані нижче (не в масштабі):
Ви вирішили допомогти Гаррі вирішити цю проблему, обчисливши простий (не самоперетинний) багатокутник з вертикальними і горизонтальними сегментами, який повністю містить рядок з якомога меншою площею. Яка площа такого багатокутника?
Формально, ви повинні обчислити нижню межу площ усіх простих ортогональних багатокутників, що містять усі відрізки [p[i], p[j]] для кожних двох сусідніх точок p[i] і p[j].
Вхідні дані
Перший рядок містить натуральне число n (4 ≤ n ≤ 100 000). Наступні n рядків містять точки (x[i], y[i]) у порядку обходу багатокутника (1 ≤ x[i], y[i] ≤ 10^6). Жодні дві послідовні точки не збігаються, і немає двох послідовних вертикальних сегментів або двох послідовних горизонтальних сегментів.
Вихідні дані
Виведіть одне невід'ємне ціле число - точну нижню межу площ усіх простих багатокутників, які оточують замкнений багатокутний рядок. Можна довести, що відповідь завжди цілочисельна.
Приклад
У прикладах 1 і 3 немає простих багатокутників з площею точно рівною 50 і 8 відповідно; однак існують прості багатокутники з площами, довільно близькими до цих значень.