Маятник

Рассмотрим математический маятник, прикрепленный к началу координат математической нитью. Начальное положение маятника (-r, 0). Если маятник отпустить, то он начнет колебаться, описывая полуокружность. Теперь представим себе, что в плоскость вбито несколько математических гвоздиков. Движение маятника в этом случае будет более сложным, но, в конце концов, он также начнет совершать некоторые периодические колебания.

Для нашего идеального математического мира считаются выполненными следующие условия:
    гвоздики и нить имеют нулевую толщину;
    энергия маятника не теряется (т.е. трение отсутствует);
    маятник никогда не сталкивается с гвоздиками (с ними входит в соприкосновение только нить);
    нить изгибается только при соприкосновении с гвоздиком.

Ваша задача состоит в том, чтобы промоделировать движение маятника и вычислить длину установившейся орбиты.

Вниманию тех, кто боится физики! Единственный физический факт, необходимый для решения этой задачи, таков: маятник никогда не поднимается выше своей начальной высоты. Следовательно, маятник либо достигнет оси x, либо будет крутиться вокруг некоторого гвоздика.

Входные данные
В первой строке входного файла записаны целое число N – количество гвоздиков (0 ≤ N ≤ 500) и вещественное число r – длина нити. В каждой из следующих N строк через пробел указаны координаты одного из гвоздиков.

Выходные данные
Выведите в выходной файл длину одного цикла периодической орбиты, по которой станет качаться маятник. Учитывать расстояние, пройденное маятником до того, как он вышел на эту орбиту, не нужно. Ответ должен быть указан с точностью до двух знаков после десятичной точки.

Пример входного файла
2 16.0
3 -4
-3 -4

Пример выходного файла
87.66

Решение

Решение этой задачи напоминает построение выпуклой оболочки методом Джарвиса [Препарата 89, п. 3.3.3]. Рассмотрим вектор (-r, 0), отложенный от начала координат. Будем поворачивать этот вектор против часовой стрелки. В какой-то момент времени он может зацепиться за один из гвоздиков, расстояние до которых меньше длины поворачиваемого вектора. А именно, он зацепится за тот из этих гвоздиков (пусть он имеет номер k₁), угол поворота до которого минимален.

На следующем шаге откладываем текущий вектор от гвоздя k₁, уменьшаем его длину на расстояние от начала координат до этого гвоздя и продолжаем процесс поворота. Т.е. среди всех гвоздей, расстояние до которых меньше текущей длины вектора, найдем тот (с номером k₂), угол поворота до которого минимален. Затем продолжим процедуру, перейдя в гвоздь k₂, и т.д. Для нахождения углов можно использовать свойства скалярного произведения.

Описанный процесс может закончиться в двух случаях. Во-первых, на очередном шаге может не найтись гвоздя, за который зацепится вектор. В этом случае маятник будет вращаться вокруг последнего из гвоздей по окружности, длину которой легко найти. Во-вторых, при повороте вокруг очередного гвоздя нужно проверять, не поднялся ли конец маятника выше оси x. Для этого можно просто добавить в массив гвоздей точки пересечения оси x c окружностью, радиус которой равен текущей длине вектора. Если вектор зацепится за такую точку, то это означает, что маятник в этой точке остановится и начнет движение в обратную сторону по той же траектории. Значит, если мы на каждом шаге будем подсчитывать текущую длину траектории конца вектора, то для нахождения длины циклической орбиты маятника останется умножить полученную длину на два.