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

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

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

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост поднят. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует три команды: Вперёд n (где n — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Направо m (где m — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке; Опустить хвост, означающая переход в режим рисования.
Запись Повтори k [Команда1 Команда2 ... КомандаS] означает, что последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм:
Вперёд 100 Направо 90 Вперёд 100 Направо 45 Опустить хвост Повтори 10 [Вперёд 30 Направо 90].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.

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

882

Пояснение

Решение:

Хвост поднят, поэтому Вперёд 100 Направо 90 Вперёд 100 ничего не рисует — Черепаха просто оказывается в точке $(100;100)$ . После Направо 45 голова смотрит под углом $-45^{\circ}$ к оси $Ox$ , и хвост опускается.

Цикл Повтори 10 [Вперёд 30 Направо 90] замыкается уже за 4 команды: рисуется квадрат со стороной 30, повёрнутый на $45^{\circ}$ , с вершинами $(100;100)$ , $(100+15\sqrt{2};\,100-15\sqrt{2})$ , $(100;\,100-30\sqrt{2})$ , $(100-15\sqrt{2};\,100-15\sqrt{2})$ .

У такого квадрата одна диагональ горизонтальна, другая вертикальна, а стороны имеют угловые коэффициенты $\pm 1$ . Поэтому точка лежит строго внутри тогда и только тогда, когда $|x-100|+|y-c|\lt 15\sqrt{2}$ , где $c=100-15\sqrt{2}$ — ордината центра.

Обозначим $t=100-y$ ; условие превращается в $|x-100|+\bigl|15\sqrt{2}-t\bigr|\lt 15\sqrt{2}$ :

при $t\le 15\sqrt{2}\approx 21{,}21$ , то есть $t=1,\dots,21$ , получаем $|x-100|\lt t$ — ровно $2t-1$ точек;
при $t\gt 15\sqrt{2}$ , то есть $t=22,\dots,42$ , получаем $|x-100|\lt 30\sqrt{2}-t\approx 42{,}43-t$ — ровно $85-2t$ точек.

$\sum\limits_{t=1}^{21}(2t-1)=21^{2}=441$ и $\sum\limits_{t=22}^{42}(85-2t)=41+39+\dots+1=21^{2}=441$ .

Всего $441+441=882$ . Проверим программой:

from math import sin, cos, radians

P = [(0.0, 0.0)]
x = y = 0.0
a = 90.0                      # голова смотрит вдоль оси Oy

def F(n):                     # Вперёд n
    global x, y
    x = round(x + n * cos(radians(a)), 9)   # round убирает шум float
    y = round(y + n * sin(radians(a)), 9)
    P.append((x, y))

def R(m):                     # Направо m
    global a
    a -= m

F(100); R(90); F(100); R(45)  # хвост поднят - это не рисуется
P = [(x, y)]                  # опустили хвост
for i in range(4):            # квадрат замыкается за 4 команды
    F(30); R(90)

def inside(px, py):           # фигура выпуклая, обход по часовой стрелке
    for i in range(len(P) - 1):
        x1, y1 = P[i]; x2, y2 = P[i + 1]
        if (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1) >= -1e-9:
            return False      # точка на линии или снаружи
    return True

xs = [p[0] for p in P]; ys = [p[1] for p in P]
print(sum(inside(px, py)
          for px in range(int(min(xs)) - 1, int(max(xs)) + 2)
          for py in range(int(min(ys)) - 1, int(max(ys)) + 2)))

Ответ: 882