Фермер Джон установил новую доильную машину.
Она берёт так много энергии, что в амбаре часто выключается свет.
Это случается так часто, что Беси запомнила карту амбара.
Это позволяет ей быстрее находить путь к выходу в темноте.
Теперь ей интересно узнать насколько дольше её путь в темноте.
Амбар описывается простым (несамопересекающимся) многоугольником
с целочисленными вершинами \((x_1, y_1) \ldots (x_n, y_n)\) перечисленными
в порядке обхода по часовой стрелке. Его рёбра составляются чередующимися
горизонтальными (параллельными оси Х) и вертикальными (параллельными оси Y)
отрезками. Первое ребро может быть как горизонтальным, так и вертикальным.
Выход расположен в точке \((x_1, y_1)\). Беси начинает в некоторой вершине
\((x_i, y_i)\) для \(i > 1\). Она идёт только по периметру амбара,
по часовой стрелке или против часовой стрелки, потенциально изменяя направления движения,
в любой вершине. Её цель - пройти минимальное расстояние и добраться до выхода.
Это довольно просто, когда свет включён - просто выбрать между движением по
часовой стрелке и движением против часовой стрелки.
Когда свет выключается, Беси в панике забывает вершину, в которой она
находится. К счастью, она помнит точную карту амбара и поэтому она может
вычислить свою позицию, двигаясь и опираясь на свои ощущения. Когда она
находится в вершине, она может сказать это левый поворот или правый поворот,
и является ли вершина выходом. Когда она идёт по ребру амбара, она может
определить точную длину ребра после того, как пройдёт всё ребро.
В общем сначала Беси двигается, чтобы определить, где она находится, а затем
чтобы добраться к выходу за минимальное из оставшихся расстояний.
Помогите Беси определить минимальное количество, на которое возрастёт её
путь в худшем случае при движении в темноте, по сравнению с движением
при свете, полагая, что она движется оптимально в каждом случае.
Оптимальная стратегия - такая, которая минимизирует увеличение расстояния
в худшем случае.
ФОРМАТ ВВОДА (файл lightsout.in):
Первая строка ввода содержит \(N\) (\(4 \leq N \leq 200\)). Каждая из последующих
\(N\) строк содержит по два целых числа, описывающих точки \((x_i, y_i)\) в почасовом
порядке обхода. Все целые числа \(-100,000 \ldots 100,000\).
ФОРМАТ ВЫВОДА (файл lightsout.out):
Минимально возможное для худшего случая увеличение длины оптимального пути
при походе в темноте по сравнению с походом при свете.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0 0
0 10
1 10
1 0
|
2
|