Задание 6 ЕГЭ: целые точки в объединении фигур

Черепаха: целые точки в объединении прямоугольников. Тема номера — исполнитель черепаха. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

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

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

Черепахе был дан для исполнения следующий алгоритм.

Повтори 9 [Вперёд 17 Направо 90 Вперёд 26 Направо 90]
Поднять хвост
Вперёд 2 Направо 90 Вперёд 19 Налево 90
Опустить хвост
Повтори 2 [Вперёд 57 Направо 90 Вперёд 10 Направо 90]

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

Решение

Одна итерация цикла рисует две стороны прямоугольника и поворачивает Черепаху на 180°, поэтому за две итерации прямоугольник замыкается, а остальные повторы обводят ту же линию.

Первая фигура: 0 ≤ x ≤ 26, 0 ≤ y ≤ 17. Повторений 9 — нечётное число, после цикла Черепаха в точке (26; 17), голова направлена вниз.

Переезд без рисования приводит её в точку (7; 15), голова направлена вниз. Вторая фигура (повторений 2): −3 ≤ x ≤ 7, −42 ≤ y ≤ 15.

Точек строго внутри первой фигуры (26 − 1) · (17 − 1) = 400, второй — (10 − 1) · (57 − 1) = 504. Общая часть 0 ≤ x ≤ 7, 0 ≤ y ≤ 15: строго внутри неё (7 − 1) · (15 − 1) = 84 точки, они посчитаны дважды.

Кроме того, внутри первой фигуры проходит часть контура второй — на ней 21 целых точка, а внутри второй фигуры — 21 точка контура первой. Эти точки лежат на линиях, их вычитаем: 400 + 504 − 84 − 21 − 21 = 778.

from math import cos, sin, radians

def run(prog):
    # контуры нарисованных фигур: вершины до первого возвращения в начальную точку
    x = y = 0
    ang = 90                                   # голова вдоль оси ординат
    paths, cur = [], [(0, 0)]
    for cmd, n in prog:
        if cmd in ("fd", "bk"):
            d = n if cmd == "fd" else -n
            x += round(d * cos(radians(ang)))   # повороты кратны 90°: смещения целые
            y += round(d * sin(radians(ang)))
            if cur is not None:
                cur.append((x, y))
        elif cmd == "rt":
            ang -= n
        elif cmd == "lt":
            ang += n
        elif cmd == "up":
            paths.append(cur)
            cur = None
        elif cmd == "down":
            cur = [(x, y)]
    if cur is not None:
        paths.append(cur)
    return [f[:f.index(f[0], 1)] for f in paths]

prog = (9 * [("fd", 17), ("rt", 90), ("fd", 26), ("rt", 90)]
        + [("up", 0)]
        + [("fd", 2), ("rt", 90), ("fd", 19), ("lt", 90)]
        + [("down", 0)]
        + 2 * [("fd", 57), ("rt", 90), ("fd", 10), ("rt", 90)])

boxes = []
for f in run(prog):
    xs = [q[0] for q in f]
    ys = [q[1] for q in f]
    boxes.append((min(xs), max(xs), min(ys), max(ys)))   # x1, x2, y1, y2
print(boxes)

def inside(b, x, y):                           # внутри или на границе
    return b[0] <= x <= b[1] and b[2] <= y <= b[3]

def strictly(b, x, y):                         # строго внутри
    return b[0] < x < b[1] and b[2] < y < b[3]

count = 0
for x in range(min(b[0] for b in boxes), max(b[1] for b in boxes) + 1):
    for y in range(min(b[2] for b in boxes), max(b[3] for b in boxes) + 1):
        if any(inside(b, x, y) for b in boxes) and \
                not any(inside(b, x, y) and not strictly(b, x, y) for b in boxes):
            count += 1
print(count)

Решить такую задачу — новый вариант с проверкой