Задача . Lights Out

Амбар описан простым (несамопересекающимся прямоугольником) с вершинами в целочисленных координатах \((x_1, y_1) \ldots (x_n, y_n)\) перечисленных по часовой стрелке. Его рёбра чередуются между горизонтальными (параллельными оси Х и вертикальными - параллельными оси Y). Первое ребро может быть как вертикальным, так и горизонтальным. Выход расположен в точке \((x_1, y_1)\). Беси начинает внутри амбара, в одной из некоторых вершин \((x_i, y_i)\) для \(i > 1\). Она может двигаться только по периметру амбара, по часовой стрелке либо против часовой стрелки. Её цель - пройти минимальное расстояние до выхода. Это относительно легко, когда свет включён. Поскольку она просто должна выбрать какой путь короче от текущего положения до выхода - по часовой стрелке или против часовой стрелки.

Когда свет выключается, Беси паникует и забывает вершину, в которой она находится. К счастью, она всё ещё помнит точную карту амбара, поэтому она может вычислить свою позицию, двигаясь по периметру и используя свои ощущения. Когда она стоит в вершине (включая свою начальную вершину), она может ощутить внутренний угол при этой вершине. и также она может сказать является ли эта вершина выходом. Когда она движется вдоль амбара, она может определить точную длину ребра, по которому прошла. Беси двигается в соответствии со следующей стратегией: она движется по часовой стрелке по периметру амбара, до тех пор, пока она не ощутит достаточное количество углов и рёбер, чтобы определить, в какой вершине она сейчас находится. В этой точке она легко может вычислить, как ей быстрее добраться до выхода - продолжив движение по часовой стрелке или переключившись на движение против часовой стрелки.

Помогите Беси определить наибольшую величину, на которую возрастёт её путь к выходу в темноте, по сравнению с путём при свете (рассмотрев все возможные положения стартовой вершины).

2