Гасіть світло (Платина)#10603
Фермер Джон встановив у своєму корівнику нову сучасну доїльну машину, але вона споживає так багато електроенергії, що іноді призводить до відключення електрики! Це трапляється настільки часто, що Бессі вивчила карту корівника напам'ять, завдяки чому їй легше знаходити вихід з корівника в темряві. Однак їй цікаво, як відключення електрики впливають на її здатність швидко покинути корівник. Наприклад, вона хоче зрозуміти, наскільки далі їй, можливо, доведеться йти в темряві, щоб знайти вихід.
Корівник описується простим (таким, що не перетинає сам себе) многокутником з цілочисельними вершинами (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 до 10^5.
Виведіть мінімально можливу величину в найгіршому випадку, на яку оптимальна відстань, пройдена Бессі в темряві, перевищує оптимальну відстань, пройдену нею при включеному світлі. Найгірший випадок розглядається за всіма можливими вершинами, в яких Бессі може почати рух.
У цьому прикладі Бессі може визначити, що спочатку перебуває у внутрішньому куті. Однак, оскільки всі кути в цьому прикладі є внутрішніми кутами, ця інформація мало їй допомагає.
Одна з оптимальних стратегій — просто рухатися за годинниковою стрілкою. Ця стратегія є оптимальною, якщо вона починає рух з вершини або , і додає лише одиниці відстані, якщо вона починає рух з вершини .
Приклад 1