Проста оболонка#10886
Гаррі намагався створити прості ортогональні багатокутники для своєї домашньої роботи з геометрії, але його алгоритм, схоже, має деякі проблеми. Після кількох годин налагодження він нарешті зрозумів, у чому проблема: багатокутники, які він генерував, можуть містити самоперетини, що зовсім не входило в його плани!
Зокрема, "багатокутники", створені Гаррі, представлені списком точок p_i = (x_i, y_i), що утворюють замкнений багатокутний ланцюг. Цей ланцюг може містити самоперетини. Сегменти, утворені кожними двома послідовними точками (x_i, y_i) і (x_j, y_j) у ланцюзі, є або вертикальними, або горизонтальними.
Полігональні ланцюги для тестових прикладів показані нижче (не в масштабі):
Ви вирішили допомогти Гаррі вирішити цю проблему, обчисливши простий (не самоперетинний) багатокутник з вертикальними і горизонтальними сегментами, який повністю містить ланцюг з якомога меншою площею. Яка площа такого багатокутника?
Формально, ви повинні обчислити нижню межу площ усіх простих ортогональних багатокутників, що містять усі відрізки [p_i, p_j] для кожних двох сусідніх точок p_i і p_j.
Перший рядок містить натуральне число (4 \leq n \leq 100000). Наступні рядків містять точки (x_i, y_i) у порядку обходу багатокутника (1 \leq x_i, y_i \leq 10^6). Жодні дві послідовні точки не збігаються, і немає двох послідовних вертикальних сегментів або двох послідовних горизонтальних сегментів.
Виведіть одне невід'ємне ціле число - точну нижню межу площ усіх простих багатокутників, які оточують замкнений багатокутний ланцюг. Можна довести, що відповідь завжди цілочисельна.
Приклад 1
Приклад 2
Приклад 3
У прикладах і немає простих багатокутників з площею точно рівною і відповідно; однак існують прості багатокутники з площами, довільно близькими до цих значень.