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

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

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

Исполнитель Цапля действует на плоскости с декартовой системой координат. В начальный момент Цапля находится в начале координат, её клюв направлен вдоль положительного направления оси ординат, клюв опущен. При опущенном клюве Цапля оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует три команды: Вперёд n (где n - целое число), вызывающая передвижение Цапли на n единиц в том направлении, куда указывает её клюв; Направо m (где m - целое число), вызывающая изменение направления движения на m градусов по часовой стрелке; Дуга r, а, b (где r, а, b - целые числа), вызывающая передвижение Цапли из текущей точки с координатами (х, у) по дуге полуокружности с центром в точке с координатами (

x + a ,

y + b

) и радиусом r, движение по полуокружности идёт по часовой стрелке.

Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз.

Цапле был дан для исполнения следующий алгоритм:
Повтори 7 [Дуга 4, 0, 4 Дуга 4, 4, 0 Дуга 4, 0, -4 Дуга 4, -4, 0].

Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.

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

153

Пояснение

Решение:

Разберём команду Дуга r, a, b: центр полуокружности — точка $(x+a;\,y+b)$ , радиус $r$ , движение по часовой стрелке. Конечная точка симметрична начальной относительно центра, то есть Цапля смещается на $(2a;\,2b)$ , а сама дуга выпирает в сторону, перпендикулярную этому смещению.

Стартуем из $(0;0)$ :

Дуга 4, 0, 4 — центр $(0;4)$ , из $(0;0)$ по часовой стрелке в $(0;8)$ ; дуга выпирает влево, до точки $(-4;4)$ ;
Дуга 4, 4, 0 — центр $(4;8)$ , из $(0;8)$ в $(8;8)$ ; дуга выпирает вверх, до точки $(4;12)$ ;
Дуга 4, 0, -4 — центр $(8;4)$ , из $(8;8)$ в $(8;0)$ ; дуга выпирает вправо, до точки $(12;4)$ ;
Дуга 4, -4, 0 — центр $(4;0)$ , из $(8;0)$ в $(0;0)$ ; дуга выпирает вниз, до точки $(4;-4)$ .

Контур замкнулся за один повтор, остальные шесть его лишь обводят. Получилась «розетка»: квадрат $[0;8]\times[0;8]$ , к каждой стороне которого снаружи приставлен полукруг радиуса 4. Стороны квадрата — не граница фигуры, они проходят внутри неё; граница — только четыре полуокружности.

Значит целая точка лежит строго внутри, если она попадает в квадрат или в один из полукругов и при этом не лежит ровно на полуокружности:

n = 0
for x in range(-5, 14):
    for y in range(-5, 14):
        kv = 0 <= x <= 8 and 0 <= y <= 8                      # квадрат 8x8
        L  = x <= 0 and x * x + (y - 4) ** 2 <= 16            # левый полукруг
        V  = y >= 8 and (x - 4) ** 2 + (y - 8) ** 2 <= 16     # верхний
        Pr = x >= 8 and (x - 8) ** 2 + (y - 4) ** 2 <= 16     # правый
        N  = y <= 0 and (x - 4) ** 2 + y * y <= 16            # нижний
        gr = (x <= 0 and x * x + (y - 4) ** 2 == 16) or \
             (y >= 8 and (x - 4) ** 2 + (y - 8) ** 2 == 16) or \
             (x >= 8 and (x - 8) ** 2 + (y - 4) ** 2 == 16) or \
             (y <= 0 and (x - 4) ** 2 + y * y == 16)          # точка лежит на дуге
        if (kv or L or V or Pr or N) and not gr:
            n += 1
print(n)

Программа печатает 153. Для контроля: площадь фигуры равна

8^{2}+4\cdot\dfrac{\pi\cdot 4^{2}}{2}=64+32\pi\approx 164{,}5

. Ответ: 153