Задача № 307
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n — целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m — целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.
Запись Повтори k [Команда1 Команда2 ... КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Повтори 2 [Вперёд 14 Налево 270 Назад 12 Направо 90]
Поднять хвост
Вперёд 9 Направо 90 Назад 7 Налево 90
Опустить хвост
Повтори 2 [Вперёд 13 Направо 90 Вперёд 6 Направо 90]
Определите, сколько точек с целочисленными координатами находятся внутри объединения фигур, ограниченного заданными алгоритмом линиями, включая точки на линиях.
Решение
Решим задачу с помощью модуля Python Turtle. Черепаха нарисует фигуру. После этого программа перебирает все точки на сетке, чтобы узнать, какие из них попадают внутрь закрашенной области, и считает их количество.
from math import ceil, floor
from turtle import *
# Устанавливаем красный цвет линии и заливки
color("red")
# Отключаем анимацию
tracer(0)
# Масштаб, увеличиваем изображение
z = 20
# Повернуть черепаху на 90 градусов влево
# По условию черепаха смотрит вверх
left(90)
# Запоминаем контур фигуры
begin_poly()
# Включаем заливку
begin_fill()
# Рисуем фигуру из условия задачи
for i in range(2):
forward(14 * z)
left(270)
backward(12 * z)
right(90)
# Заливаем первую часть фигуры
end_fill()
# Сдвигаем черепаху (по условию задачи)
up()
forward(9 * z)
right(90)
backward(7 * z)
left(90)
down()
# Рисуем вторую фигуру
begin_fill()
for i in range(2):
forward(13 * z)
right(90)
forward(6 * z)
right(90)
end_fill()
# Завершаем контур фигуры
end_poly()
# Поднимаем хвост, чтобы больше ничего не рисовать
up()
# Получаем контур нарисованной фигуры
xs, ys = zip(*get_poly())
# Рассчитаем координаты, нарисованной фигуры
x1 = floor(min(xs)) // z * z + z
x2 = ceil(max(xs)) // z * z + z
y1 = floor(min(ys)) // z * z + z
y2 = ceil(max(ys)) // z * z + z
# Получаем объект холста для анализа точек
canvas = getcanvas()
# Считаем ответ — количество точек внутри фигуры
count = 0
# Перебираем все точки с целочисленными координатами на сетке
for x in range(x1, x2, z):
for y in range(y1, y2, z):
goto(x, y)
# Проверяем наличие фигуры по координатам
if canvas.find_overlapping(x, -y, x, -y):
count += 1 # Если да, увеличиваем счетчик
dot(5, 'blue') # Рисуем синюю точку (эта точка внутри фигуры)
else:
dot(3, 'gray') # Внешние точки рисуем серым
print(count) # Выводим ответ — сколько точек попало внутрь фигуры
done() # Завершаем программу
После запуска кода появится изображение объединённой фигуры. В терминале программа выведет количество синих точек, которые нужно посчитать по условию задачи.
Ответ: 251.