Задание №6 — Анализ алгоритмов для исполнителя

#69460Задание №6ФИПИ

Анализ алгоритмов и исполнители

Исполнитель Цапля действует на плоскости с декартовой системой координат. В начальный момент Цапля находится в начале координат, её клюв направлен вдоль положительного направления оси ординат, клюв опущен. При опущенном клюве Цапля оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует три команды: Вперёд n (где n — целое число), вызывающая передвижение Цапли на n единиц в том направлении, куда указывает её клюв; Направо m (где m — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке; Дуга r, a, b (где r, a, b — целые числа), вызывающая передвижение Цапли из текущей точки с координатами (х, у) по дуге полуокружности с центром в точке с координатами (х + a, у + b) и радиусом r, движение по полуокружности идёт по часовой стрелке.
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз.
Цапле был дан для исполнения следующий алгоритм:
Направо 180 Вперёд 2 Направо 90 Вперёд 80 Направо 90 Вперёд 2 Повтори 8 [Дуга 5, 5, 0].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.

Правильный ответ

391

Пояснение

Решение:

Направо 180 Вперёд 2 переводит Цаплю из $(0;0)$ в $(0;-2)$ . Направо 90 направляет клюв вдоль отрицательного направления оси $Ox$ , Вперёд 80 даёт $(-80;-2)$ . Ещё одно Направо 90 — клюв вверх, Вперёд 2 даёт $(-80;0)$ .

Команда Дуга 5, 5, 0 из точки $(x;y)$ описывает полуокружность радиуса 5 с центром $(x+5;\,y)$ по часовой стрелке: конечная точка — $(x+10;\,y)$ , а дуга выпирает вверх. Восемь таких дуг ведут из $(-80;0)$ в $(0;0)$ и замыкают линию.

Итак, фигура — прямоугольник $[-80;0]\times[-2;0]$ , на верхней стороне которого лежат восемь полукругов радиуса 5 с центрами $(-75;0)$ , $(-65;0)$ , $\dots$ , $(-5;0)$ . Верхняя сторона прямоугольника проходит внутри фигуры, а точки стыка соседних дуг $(-70;0)$ , $(-60;0)$ , $\dots$ , $(-10;0)$ лежат на границе и не считаются.

C = [-75, -65, -55, -45, -35, -25, -15, -5]   # центры полуокружностей, r = 5
n = 0
for x in range(-86, 7):
    for y in range(-3, 7):
        pr = -80 <= x <= 0 and -2 <= y <= 0                          # прямоугольник
        pk = any(y >= 0 and (x - c) ** 2 + y * y <= 25 for c in C)   # полукруги
        gr = any(y >= 0 and (x - c) ** 2 + y * y == 25 for c in C) \
             or (pr and (x == -80 or x == 0 or y == -2))             # точки на линии
        if (pr or pk) and not gr:
            n += 1
print(n)

Программа печатает 391. Для контроля: площадь равна

80\cdot 2+8\cdot\dfrac{\pi\cdot 5^{2}}{2}=160+100\pi\approx 474{,}2

. Ответ: 391