Задание №6 — Анализ алгоритмов для исполнителя
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды; Вперёд n (где n — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Направо m (где m — целое число), вызывающая изменение направления движения на m градусов
по часовой стрелке.
Запись Повтори k [Команда1 Команда2 ... КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Повтори 21 [Вперёд 31 Направо 60].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.
Правильный ответ
2476
Пояснение
Решение:
Поворот направо на 60° — это внешний угол правильного шестиугольника, поэтому каждые шесть команд Вперёд 31 Направо 60 замыкают правильный шестиугольник со стороной 31. За 21 повторение Черепаха обходит один и тот же шестиугольник три с половиной раза — новых линий не появляется.
Найдём вершины. Стартовое направление — вверх, дальше направление каждый раз поворачивается на 60° по часовой стрелке:
Шестиугольник выпуклый и обходится по часовой стрелке, поэтому точка лежит строго внутри тогда и только тогда, когда для каждой стороны векторное произведение строго отрицательно. Перебираем целые точки описанного прямоугольника:
from math import sin, cos, radians
p = []
x = y = 0.0
ang = 0.0
for i in range(6):
p.append((x, y))
x += 31 * sin(radians(ang))
y += 31 * cos(radians(ang))
ang += 60
def inside(px, py):
for i in range(6):
x1, y1 = p[i]
x2, y2 = p[(i + 1) % 6]
if (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1) >= -1e-9:
return False
return True
print(sum(inside(px, py) for px in range(0, 55) for py in range(-16, 47)))
Программа выводит 2476.
Проверим правдоподобность: площадь шестиугольника равна , при этом 32 целые точки лежат на левой стороне и в счёт не идут. Результат согласуется с площадью.
Ответ: 2476