Задание №6. Черепаха и геометрические фигуры

Черепаха перемещается по координатной плоскости и рисует линии. В задании №6 по её командам нужно восстановить фигуру, а затем найти то, что указано в вопросе: число точек с целыми координатами, площадь или периметр. Иногда рисунок состоит из двух фигур — тогда важна их общая часть или вся занятая ими область. Один и тот же рисунок при разных вопросах даёт разные ответы.

Положение, направление и след

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

Направления движения в таблице описаны для n>0. Отрицательный аргумент меняет сторону на противоположную: например, Назад -2 действует как Вперёд 2.

Поворот отсчитывается от текущего направления, а не от оси. Например, после поворота направо от направления вниз голова смотрит влево. Запись Повтори k [...] повторяет весь блок в скобках; новый повтор начинается там, где закончился предыдущий.

Две фигуры: от команд до ответа

В задании EGE-06-0018 ↗ требуется число точек с целыми координатами в объединении двух фигур, включая границы. Алгоритм такой:

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

1. Первый прямоугольник

В одном повторе рисуются две стороны. После первого повтора Черепаха оказывается в правом верхнем углу и смотрит вниз. Второй повтор дорисовывает прямоугольник и возвращает исходное направление.

Первая фигура обозначена A. Она занимает область:

A:\quad 0 \le x \le 20,\qquad 0 \le y \le 10.

2. Переход ко второй фигуре

Хвост поднят, поэтому следующие движения не добавляют сторон к рисунку. Из (0;0) Черепаха проходит 5 вверх — в (0;5). Поворот направо и движение на 9 приводят её в (9;5). Поворот налево снова направляет голову вверх. Это точка и направление начала второй фигуры.

После опускания хвоста два повтора дают вершины (9;5), (9;15), (24;15), (24;5) и возврат в (9;5). Вторая фигура обозначена B:

B:\quad 9 \le x \le 24,\qquad 5 \le y \le 15.

3. Число точек в каждой области

Целые координаты — это числа без дробной части. Например, на отрезке от 0 до 3 расположены четыре целочисленные точки: 0, 1, 2, 3. Поэтому длина отрезка и число точек на нём отличаются.

В первой фигуре для x подходит 21 значение: от 0 до 20 включительно. Для каждого из них есть 11 значений y: от 0 до 10. Во второй фигуре — 16 значений x и 11 значений y. Числа точек в этих фигурах обозначены N_A и N_B.

N_A=(20-0+1)(10-0+1)=231,
N_B=(24-9+1)(15-5+1)=176.

Если просто сложить 231 и 176, точки общей части будут учтены дважды. Общая часть — пересечение — занимает 9 \le x \le 20 и 5 \le y \le 10. В ней 12 столбцов по 6 точек:

N_{A\cap B}=(20-9+1)(10-5+1)=72.

Из общей суммы вычитается одна лишняя копия этих 72 точек. Сами точки пересечения остаются в ответе:

N_{A\cup B}=231+176-72=335.

4. Проверка перебором координат

Те же границы позволяют проверить ответ программой. Перебор охватывает весь рисунок: x от 0 до 24 и y от 0 до 15. В range правая граница не включается, поэтому в коде стоят 25 и 16.

count = 0
for x in range(0, 25):
    for y in range(0, 16):
        in_a = 0 <= x <= 20 and 0 <= y <= 10
        in_b = 9 <= x <= 24 and 5 <= y <= 15
        if in_a or in_b:
            count += 1
print(count)  # 335

Условие in_a or in_b отвечает объединению: точка подходит хотя бы одной фигуре. Каждая пара координат проверяется один раз, поэтому дополнительное вычитание пересечения в этой программе не нужно. Для пересечения использовалось бы in_a and in_b.

Другой вопрос — другой расчёт

В задании EGE-06-0003 ↗ дан тот же алгоритм, но требуется площадь объединения. Площадь считается по длинам сторон, без прибавления единицы:

S_{A\cup B}=20\cdot10+15\cdot10-11\cdot5=295.

Для пересечения нужны только общие координаты. Например, в задании EGE-06-0026 ↗ общая область задаётся границами 14\le x\le18, 5\le y\le10. С границей в ней 5\cdot6=30 целочисленных точек.

Периметр — длина границы нужной области. В задании EGE-06-0066 ↗ пересечение — прямоугольник со сторонами 8 и 2, поэтому периметр равен 2(8+2)=20. Длины всех нарисованных отрезков складывать нельзя: часть линий не относится к границе пересечения, а некоторые обводятся повторно.

Повторное рисование и наклонные стороны

В том же задании EGE-06-0066 первый блок Повтори 7 [Вперёд 5 Направо 90 Вперёд 11 Направо 90] несколько раз проходит по одному прямоугольнику. Два повтора замыкают контур; после шести повторов Черепаха снова в начале и смотрит вверх. Седьмой повтор заканчивается в (11;5) с направлением вниз. Следующая фигура строится из этого состояния. Удаление «лишних» повторов сохранило бы рисунок первого прямоугольника, но изменило бы дальнейший маршрут.

При поворотах на 45^\circ стороны могут оказаться наклонными. В задании EGE-06-0008 ↗ получается квадрат, стоящий на вершине. Прямоугольная рамка вокруг него содержит лишние точки. Подходящий способ — считать целые точки по горизонтальным рядам: для каждого значения y определить допустимые x. Этот пример и исключение границ разобраны в статье «Координаты, границы и геометрические области».

Наклонная фигура не обязательно является квадратом. В задании EGE-06-0023 ↗ получается параллелограмм: допустимые координаты каждого ряда определяются по его собственным сторонам.

Подсчёт по рядам подходит и для ступенчатого контура, как в задании EGE-06-0001 ↗. Его стороны идут вдоль осей, но ширина внутренних рядов меняется: при y=-9,\ldots,-1 допустимы x=-9,\ldots,9, а при y=0,\ldots,9 — только x=-9,\ldots,-1. Границы исключены условием, поэтому получается 9\cdot19+10\cdot9=261 точка. Общая рамка фигуры дала бы лишние точки справа вверху.

Возможные ловушки

Ниже несколько особенностей условий, которые могут изменить построение или ответ.

• «Назад» принято за разворот. В EGE-06-0002 ↗ после Налево 270 голова направлена вправо, а Назад 12 ведёт влево. Следующий поворот по-прежнему отсчитывается от направления головы вправо. При замене движения разворотом вторая половина фигуры окажется в другом месте.
• Пропущен знак расстояния. В EGE-06-0029 ↗ записано Назад -2. Это движение на 2 вперёд: из начала координат с головой вверх Черепаха попадёт в (0;2). Подмена команды на Назад 2 сдвинет вторую фигуру вниз вместо вверх.
• Соединены фигуры при поднятом хвосте. В основном примере EGE-06-0018 ↗ путь до (9;5) не рисуется. Он меняет начало второй фигуры, но не добавляет новую границу к первой.
• Рисунок замкнулся — исполнение остановлено. В EGE-06-0066 ↗ одинаковый след после двух и семи повторов не означает одинаковое конечное положение. Перед переходом ко второй фигуре нужны координаты и направление после всех повторов.
• Площадь подменяет число точек. У одинаковых фигур в EGE-06-0003 ↗ и EGE-06-0018 ↗ ответы 295 и 335: спрашиваются разные величины. Для точек отдельно учитываются крайние целые координаты.
• Граница включена вопреки условию. В EGE-06-0008 ↗ точки на линиях исключаются. Точка на наклонной стороне тоже граничная. Увеличение рисунка помогает увидеть её, но принадлежность подтверждается координатами и уравнением стороны.