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

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

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

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

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

250

Пояснение

Решение:

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

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

Фигура — прямоугольник $[-48;0]\times[-3;0]$ , на верхней стороне которого лежат шесть полукругов радиуса 4 с центрами $(-44;0)$ , $(-36;0)$ , $(-28;0)$ , $(-20;0)$ , $(-12;0)$ , $(-4;0)$ . Верхняя сторона прямоугольника проходит внутри фигуры, а точки стыка дуг $(-40;0)$ , $(-32;0)$ , $(-24;0)$ , $(-16;0)$ , $(-8;0)$ лежат на границе и не считаются.

C = [-44, -36, -28, -20, -12, -4]             # центры полуокружностей, r = 4
n = 0
for x in range(-54, 7):
    for y in range(-4, 6):
        pr = -48 <= x <= 0 and -3 <= y <= 0                          # прямоугольник
        pk = any(y >= 0 and (x - c) ** 2 + y * y <= 16 for c in C)   # полукруги
        gr = any(y >= 0 and (x - c) ** 2 + y * y == 16 for c in C) \
             or (pr and (x == -48 or x == 0 or y == -3))             # точки на линии
        if (pr or pk) and not gr:
            n += 1
print(n)

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

48\cdot 3+6\cdot\dfrac{\pi\cdot 4^{2}}{2}=144+48\pi\approx 294{,}8

. Ответ: 250