Фермер Джон установил новую доильную машину. Она берёт так много энергии, что в амбаре часто выключается свет. Это случается так часто, что Беси запомнила карту амбара. Это позволяет ей быстрее находить путь к выходу в темноте. Теперь ей интересно узнать насколько дольше её путь в темноте.
Амбар описывается простым (несамопересекающимся) многоугольником с целочисленными вершинами (x[1]
, y[1]
) ... (x[n]
, y[n]
) перечисленными в порядке обхода по часовой стрелке. Его рёбра составляются чередующимися горизонтальными (параллельными оси Х) и вертикальными (параллельными оси Y) отрезками. Первое ребро может быть как горизонтальным, так и вертикальным. Выход расположен в точке (x[1]
, y[1]
). Беси начинает в некоторой вершине (x[i]
, y[i]
) для i > 1. Она идёт только по периметру амбара, по часовой стрелке или против часовой стрелки, потенциально изменяя направления движения, в любой вершине. Её цель - пройти минимальное расстояние и добраться до выхода. Это довольно просто, когда свет включён - просто выбрать между движением по часовой стрелке и движением против часовой стрелки.
Когда свет выключается, Беси в панике забывает вершину, в которой она находится. К счастью, она помнит точную карту амбара и поэтому она может вычислить свою позицию, двигаясь и опираясь на свои ощущения. Когда она находится в вершине, она может сказать это левый поворот или правый поворот, и является ли вершина выходом. Когда она идёт по ребру амбара, она может определить точную длину ребра после того, как пройдёт всё ребро. В общем сначала Беси двигается, чтобы определить, где она находится, а затем чтобы добраться к выходу за минимальное из оставшихся расстояний.
Помогите Беси определить минимальное количество, на которое возрастёт её путь в худшем случае при движении в темноте, по сравнению с движением при свете, полагая, что она движется оптимально в каждом случае. Оптимальная стратегия - такая, которая минимизирует увеличение расстояния в худшем случае.
Первая строка содержит n (4 ≤ n ≤ 200). Каждая из последующих n строк содержит по два целых числа, описывающих точки (x[i]
, y[i]
) в почасовом порядке обхода. Все целые числа -10^5
... 10^5
.
Минимально возможное для худшего случая увеличение длины оптимального пути при походе в темноте по сравнению с походом при свете.
Одна оптимальная стратегия - двигаться по часовой стрелке - это оптимально, если начинать в вершинах 3 или 4 и добавляет 2 единицы расстояния, если она начнёт в вершине 2.