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

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

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

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

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

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

Пояснение

Решение:

Соберём повороты между соседними отрезками. Внутри цикла между двумя шагами накапливается $60^\circ+30^\circ=90^\circ$ ; столько же получается перед командой Вперёд 11 ( $60^\circ+30^\circ$ ) и в последнем цикле ( $90^\circ$ ). Значит, Черепаха рисует пять отрезков длиной 8, 8, 11, 8 и 8, каждый раз поворачивая ровно на прямой угол.

Последний отрезок идёт в том же направлении, что и первый, и лежит с ним на одной прямой, продолжая её назад. Поэтому ломаная замыкается в прямоугольник со сторонами 11 и 8 с вершинами $(-1{,}5;\ 1{,}5\sqrt3)$ , $(4;\ -4\sqrt3)$ , $(4-4\sqrt3;\ -4-4\sqrt3)$ , $(-1{,}5-4\sqrt3;\ -4+1{,}5\sqrt3)$ — приближённо $(-1{,}5;\,2{,}60)$ , $(4;\,-6{,}93)$ , $(-2{,}93;\,-10{,}93)$ , $(-8{,}43;\,-1{,}40)$ .

Площадь прямоугольника $11\cdot 8=88$ , а всего целых точек в нём вместе с границей 89. Две из них — $(0;0)$ (начало движения) и $(-6;0)$ — лежат ровно на сторонах, а точки на линии считать не следует, поэтому остаётся $89-2=87$ .

from math import cos, sin, radians

x = y = 0.0
h = 90.0
P = [(0.0, 0.0)]

def R(a):
    global h
    h -= a

def F(n):
    global x, y
    x += n * cos(radians(h))
    y += n * sin(radians(h))
    P.append((x, y))

R(120)
for _ in range(2):
    R(30); F(8); R(60)
R(30); F(11)
for _ in range(2):
    R(90); F(8)

poly = [P[4], P[1], P[2], P[3]]      # вершины прямоугольника 11 x 8

def inside(px, py):
    d = []
    for i in range(4):
        ax, ay = poly[i]
        bx, by = poly[(i + 1) % 4]
        d.append((bx - ax) * (py - ay) - (by - ay) * (px - ax))
    return all(t > 1e-9 for t in d) or all(t < -1e-9 for t in d)

print(sum(inside(a, b) for a in range(-20, 20) for b in range(-20, 20)))

Программа выводит 87. Ответ: 87