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