Гасне світло (Золото)#10600
Фермер Джон встановив у своєму корівнику нову сучасну доїльну машину, але вона споживає так багато електроенергії, що іноді призводить до відключення електрики! Це трапляється настільки часто, що Бессі вивчила карту корівника напам'ять, завдяки чому їй легше знаходити вихід із корівника в темряві. Однак їй цікаво, як відключення електрики впливає на її здатність швидко покинути корівник. Наприклад, вона хоче зрозуміти, наскільки далі їй, можливо, доведеться йти в темряві, щоб знайти вихід.
Корівник описується простим (таким, що не перетинає сам себе) багатокутником із цілочисельними вершинами (x_1, y_1), \ldots, (x_n, y_n), перерахованими за годинниковою стрілкою. Його сторони чергуються: горизонтальні (паралельні осі ) та вертикальні (паралельні осі ), причому перша сторона може бути будь-якого з двох типів. Вихід розташований у точці (x_1, y_1). Бессі починає рух усередині корівника, перебуваючи в одній із вершин (x_i, y_i) для i > 1. Вона може рухатися лише вздовж границі корівника — за годинниковою стрілкою або проти годинникової стрілки. Її мета — пройти якомога менший шлях, щоб дістатися виходу. При увімкненому освітленні зробити це, звісно, доволі просто: вона може рухатися від своєї поточної позиції до виходу або за годинниковою стрілкою, або проти годинникової стрілки, обираючи коротший шлях.
Одного разу світло гасне, і Бессі в паніці забуває, в якій саме вершині вона перебуває. На щастя, вона все ще пам'ятає точну карту корівника, тому може спробувати визначити своє місцезнаходження, рухаючись вздовж границі та використовуючи дотик. Щоразу, коли вона перебуває у вершині (в тому числі у своїй початковій вершині), вона може визначити точний внутрішній кут цієї вершини, а також дізнатися, чи є ця вершина виходом. Коли вона проходить вздовж сторони корівника, вона може визначити її точну довжину після того, як повністю пройде цю сторону.
Бессі обирає таку стратегію: вона рухатиметься за годинниковою стрілкою вздовж границі корівника доти, доки не відчує достатньо кутів і сторін, щоб однозначно визначити вершину, в якій вона перебуває. Після цього вона легко зможе визначити найкоротший шлях до виходу: або продовжити рух за годинниковою стрілкою, або змінити напрямок і рухатися проти годинникової стрілки.
Допоможіть Бессі визначити максимальну величину, на яку в найгіршому випадку (за всіма можливими початковими вершинами) збільшиться пройдена нею відстань при русі в темряві порівняно з рухом при увімкненому освітленні.
У першому рядку міститься ціле число n~(4 \le n \le 200). У кожному з наступних рядків містяться два цілих числа, що описують точки (x_i, y_i) у порядку обходу за годинниковою стрілкою навколо корівника. Ці цілі числа знаходяться в діапазоні -10^5 \le x_i, y_i \le 10^5.
Виведіть максимальну величину, на яку збільшиться пройдена Бессі відстань у найгіршому випадку за всіма можливими початковими вершинами при використанні стратегії, описаної в умові.
У цьому прикладі Бессі може визначити, що спочатку перебуває у вершині з кутом градусів, але не може зрозуміти, чи перебуває вона у вершині чи . Після того як вона проходить одну сторону за годинниковою стрілкою, вона або досягає виходу, або може однозначно визначити своє місцезнаходження за довжиною цієї сторони. Розглянемо пройдені нею відстані:
Якщо Бессі починає у вершині , то в темряві вона проходить одиниць: одиницю, щоб дістатися вершини , а потім ще одиниць до виходу. При увімкненому освітленні їй достатньо пройти одиниць. Таким чином, для цієї початкової вершини додаткова відстань становить одиниці.
Якщо Бессі починає у вершині , то в обох випадках вона проходить одиниць.
Якщо Бессі починає у вершині , то в обох випадках вона проходить одиницю.
Отже, різниця в найгіршому випадку за всіма можливими початковими вершинами дорівнює 12 - 10 = 2. Іншими словами, Бессі може гарантувати, що незалежно від того, де вона починає, при використанні своєї стратегії в темряві вона пройде не більше ніж на одиниці більше, ніж при увімкненому освітленні.
Приклад 1