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

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

Пример

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

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

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

Повтори 7 [Вперёд 12 Налево 90 Вперёд 66 Налево 90]
Поднять хвост
Назад 1 Налево 90 Назад 19 Направо 90
Опустить хвост
Повтори 5 [Вперёд 47 Налево 90 Вперёд 50 Налево 90]

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

Решение

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

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

Переезд без рисования приводит её в точку (−85; 13), голова направлена вниз. Вторая фигура (повторений 5): −85 ≤ x ≤ −35, −34 ≤ y ≤ 13.

Пересечение: левый край — больший из левых, правый — меньший из правых; так же по вертикали: −66 ≤ x ≤ −35, 0 ≤ y ≤ 12, стороны 31 и 12. С границей в каждом ряду по 31 + 1 точек, рядов 12 + 1: (31 + 1) · (12 + 1) = 416.

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 = (7 * [("fd", 12), ("lt", 90), ("fd", 66), ("lt", 90)]
        + [("up", 0)]
        + [("bk", 1), ("lt", 90), ("bk", 19), ("rt", 90)]
        + [("down", 0)]
        + 5 * [("fd", 47), ("lt", 90), ("fd", 50), ("lt", 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 all(inside(b, x, y) for b in boxes):
            count += 1
print(count)

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