Задание 6 ЕГЭ по информатике: исполнитель Черепаха и точки внутри фигур — разбор и примеры

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

Что проверяет задание

• умение формально исполнить алгоритм с циклом Повтори и командами перемещения;
• понимание систем координат: начальное положение и направление Черепахи, что значит «направо» и «налево»;
• аккуратный подсчёт точек решётки в прямоугольнике или многоугольнике.

Система команд

У Черепахи есть хвост: когда он опущен, при движении остаётся след. В начальный момент Черепаха находится в начале координат и смотрит вдоль положительного направления оси ординат (вверх), хвост опущен.

• Вперёд n — переместиться на n единиц в направлении движения;
• Назад n — переместиться на n единиц в противоположном направлении, не меняя направления;
• Направо m — повернуться на m градусов по часовой стрелке;
• Налево m — повернуться на m градусов против часовой стрелки;
• Поднять хвост и Опустить хвост — прекратить и возобновить рисование;
• Повтори k [команды] — выполнить команды в скобках k раз.

Типичные формулировки

1. «Определите, сколько точек с целочисленными координатами находится внутри области, ограниченной линией. Точки на линии не учитывать».
2. «… внутри области пересечения двух фигур, точки на границах учитывать».
3. «… внутри объединения фигур» или «… принадлежит хотя бы одной фигуре».
4. Фигуры с поворотами не на 90°: треугольники, шестиугольники — тогда без программы обойтись трудно.

Пошаговый метод

1. Исполните программу на бумаге, отслеживая координаты Черепахи и её направление после каждой команды. Удобно записывать направление словами: вверх, вправо, вниз, влево.
2. Определите фигуры. Для прямоугольника со сторонами вдоль осей достаточно найти диапазоны x и y.
3. Найдите нужную область. Пересечение двух прямоугольников — тоже прямоугольник: его левая граница — большая из левых, правая — меньшая из правых, аналогично по y.
4. Посчитайте точки. Если прямоугольник занимает по x отрезок [a; b], а по y — [c; d], то точек с границей (b − a + 1) · (d − c + 1), а строго внутри — (b − a − 1) · (d − c − 1).
5. Сверьтесь с моделированием на Python, если фигуры сложнее прямоугольников.

Разбор примера

Черепахе дан для исполнения алгоритм:

Повтори 2 [Вперёд 9 Направо 90 Вперёд 15 Направо 90]
Поднять хвост
Вперёд 3 Направо 90 Вперёд 5 Налево 90
Опустить хвост
Повтори 2 [Вперёд 10 Направо 90 Вперёд 8 Направо 90]

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

Шаг 1. Первая фигура. Черепаха идёт вверх на 9, поворачивает направо (теперь смотрит вправо), идёт на 15, снова направо (вниз) — на 9, направо (влево) — на 15 и возвращается в начало, глядя вверх. Это прямоугольник: x от 0 до 15, y от 0 до 9.

Шаг 2. Перемещение без следа. Вверх на 3 — точка (0; 3). Направо — смотрит вправо, вперёд на 5 — точка (5; 3). Налево — снова смотрит вверх.

Шаг 3. Вторая фигура. Из точки (5; 3) прямоугольник 10 вверх и 8 вправо: x от 5 до 13, y от 3 до 13.

Шаг 4. Пересечение. По x: от max(0, 5) = 5 до min(15, 13) = 13. По y: от max(0, 3) = 3 до min(9, 13) = 9. Пересечение — прямоугольник 8 × 6.

Шаг 5. Подсчёт. Строго внутри: x от 6 до 12 (7 значений), y от 4 до 8 (5 значений), всего 7 · 5 = 35. Вместе с границей: x от 5 до 13 (9 значений), y от 3 до 9 (7 значений), всего 9 · 7 = 63.

Ответ: 35 (без точек на линиях) и 63 (с точками на линиях).

Код на Python

Чтобы не ошибиться с поворотами, программу Черепахи можно смоделировать. Храним координаты и угол (90° — вверх), а затем проверяем все точки решётки в разумных пределах.

import math

def run(program):
    x, y, ang, pen = 0.0, 0.0, 90.0, True
    figures, cur = [], [(0, 0)]
    for cmd, arg in program:
        if cmd == 'F':                                   # Вперёд (Назад — отрицательный arg)
            x = round(x + arg * math.cos(math.radians(ang)), 9)
            y = round(y + arg * math.sin(math.radians(ang)), 9)
            if pen:
                cur.append((x, y))
        elif cmd == 'R': ang -= arg                      # Направо
        elif cmd == 'L': ang += arg                      # Налево
        elif cmd == 'UP': figures.append(cur); pen = False
        elif cmd == 'DOWN': pen = True; cur = [(x, y)]
    figures.append(cur)
    return figures

prog = [('F', 9), ('R', 90), ('F', 15), ('R', 90)] * 2 \
     + [('UP', 0), ('F', 3), ('R', 90), ('F', 5), ('L', 90), ('DOWN', 0)] \
     + [('F', 10), ('R', 90), ('F', 8), ('R', 90)] * 2
f1, f2 = run(prog)
box = lambda f: (min(p[0] for p in f), max(p[0] for p in f), min(p[1] for p in f), max(p[1] for p in f))
b1, b2 = box(f1), box(f2)
inside = lambda b, X, Y: b[0] < X < b[1] and b[2] < Y < b[3]
print(sum(inside(b1, X, Y) and inside(b2, X, Y)
          for X in range(-30, 30) for Y in range(-30, 30)))   # 35

Для произвольного многоугольника вместо проверки по прямоугольнику используют проверку «точка внутри многоугольника» (метод лучей). Другой популярный способ — нарисовать фигуры модулем turtle в крупном масштабе, отметить точки решётки командой dot и посчитать их по рисунку. Он нагляден, но подсчёт глазами долог и чреват ошибками, поэтому для прямоугольников проще формула.

Объединение фигур

Если спрашивают о точках внутри объединения, удобно воспользоваться формулой включений и исключений: число точек объединения равно сумме точек каждой фигуры минус число точек пересечения. Для примера выше с учётом границ: первая фигура содержит 16 · 10 = 160 точек, вторая — 9 · 11 = 99 точек, пересечение — 63 точки, объединение — 160 + 99 − 63 = 196. Если точки на линиях не учитываются, будьте внимательны: часть линий одной фигуры проходит внутри другой, и формула в простом виде уже не работает — надёжнее посчитать программой.

Частые ошибки

• Неверное начальное направление. Черепаха начинает, глядя вверх, а не вправо.
• Путают «Направо» и «Налево», особенно после нескольких поворотов. Записывайте направление после каждой команды.
• Забывают про поднятый хвост: перемещение без следа не образует линию и не ограничивает область.
• Ошибка на единицу. На отрезке от a до b целых точек b − a + 1, строго внутри — b − a − 1.
• Не читают, учитываются ли точки на линиях. От этого ответ меняется заметно: 35 против 63 в нашем примере.

Потренируйтесь

Попробуйте несколько программ с разными фигурами: задания № 6 в банке. Следующая тема — задание 7: объём изображений и звука.