Задача

Маятник
PENDULUM

Условие Комментарии Решение Тестовые файлы Оглавление

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

Для нашего идеального математического мира считаются выполненными следующие условия:

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

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

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

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

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

Например:

PENDULUM.IN
2 16.0
3 -4
-3 -4

PENDULUM.OUT
87.66

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

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

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

Решение

{ ----------------- Compiler directives ------------------- }
{$A+,B-,E-,F-,G-,N+,O-,P-,Q-,T-,V+,X+}
{$M 65520,0,655360}

{ ------------------ Debug mode on/off -------------------- }

{$DEFINE __DEBUG__}

{$IFDEF __DEBUG__}
{$D+,I+,L+,R+,S+,Y+}
{$ELSE}
{$D-,I-,L-,R-,S-,Y-}
{$ENDIF}
{ --------------- End Compiler directives ----------------- }

program pendulum;
type
TNails = array [1..501] of
record
                        x, y : extended;
                        end;
var
    nails : TNails;
    n, reduced : integer;
    i : integer;
    length : extended;
    x, y : extended;
    way_gone : extended;
    cur_lenght : extended;
    cur_center_x, cur_center_y : extended;
    cycle_length : extended;
    ang, smallest : extended;
    cur_i : integer;

function ArcSin (x : extended) : extended;
begin
    ArcSin := ArcTan (x / sqrt (1 - x*x));
    end;

function Distance (x1, y1, x2, y2 : extended) : extended;
begin
    Distance := sqrt (sqr (x1 - x2) + sqr (y1 - y2));
    end;

function Angle (x1, y1, x2, y2 : extended) : extended;
begin
    if (y1 = y2) and (x1 > x2)
        then Angle := 0.0
        else if (y1 = y2) and (x1 < x2)
        then Angle := pi
        else if (x1 = x2) and (y1 > y2)
        then Angle := pi / 2
        else if (x1 = x2) and (y1 < y2)
        then Angle := 3 * pi / 2
        else if (x1 > x2) and (y1 > y2)
        then Angle := ArcTan ((y1 - y2) / (x1 - x2))
        else if (x2 > x1) and (y1 > y2)
        then Angle := pi / 2 + ArcTan ((x2 - x1) / (y1 - y2))
        else if (x2 > x1) and (y2 > y1)
        then Angle := pi + ArcTan ((y2 - y1) / (x2 - x1))
            else Angle := 3 * pi / 2 + ArcTan ((x1 - x2) / (y2 - y1));
    end;

procedure Model (gone, c_x, c_y, len, a : extended);
begin
        if (abs (c_y) < len)
then
begin
                inc (n);
smallest := pi + ArcSin (abs (c_y) / len) - a;
    nails [n].x := c_x + sqrt (sqr (len) - sqr(c_y));
        nails [n].y := 0;
                    cur_i := n;
                end
            else smallest := 2*pi;
        i := 0;
        while (i < n) do begin
        inc (i);
        if ((nails [i].x = c_x) and (nails [i].y = c_y)) or
(Distance (c_x, c_y, nails [i].x, nails [i].y) > len)
then Continue;
           ang := Angle (c_x, c_y, nails [i].x, nails [i].y);
            ang := ang - a;
            if ang < 0
            then ang := ang + 2*pi;
            if ang < smallest
            then
begin
smallest := ang;
                        cur_i := i;
                    end;
        end;
    if n = reduced + 1
        then dec (n);
        if (smallest = 2*pi)
        then
            begin
                    cycle_length := 2 * pi * len;
                end
        else if cur_i = n + 1
        then
            begin
                cycle_length := 2 * (gone + smallest*len);
                end
        else
        begin
            Model (gone + smallest*len,
nails [cur_i].x, nails [cur_i].y,
len - Distance (c_x, c_y, nails [cur_i].x, nails [cur_i].y),
                            a + smallest);
        end;
    end;

begin
    assign (input, 'pendulum.in');
    reset (input);
    read (n);
    read (length);
    reduced := 0;
    for i := 1 to n do
    begin
        read (x);
            read (y);
            if (y < 0) and (sqr (x) + sqr (y) <= sqr (length))
            then
                begin
                    inc (reduced);
                        nails [reduced].x := x;
                        nails [reduced].y := y;
                    end;
        end;
    close (input);
    n := reduced;
    if (n = 0)
    then
        begin
            assign (output, 'pendulum.out');
                rewrite (output);
                writeln ((2 * pi * length) : 1 : 2);
                close (output);
                Halt (0);
            end;
cycle_length := 0;
    Model (0.0, 0.0, 0.0, length, 0.0);
    assign (output, 'pendulum.out');
    rewrite (output);
    Writeln (cycle_length : 1 : 2);
    close (output);
end.