Решение: Подсчёт точек внутри области
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен.
При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: «Вперёд $n$», где $n$ — целое число, вызывающая передвижение Черепахи на $n$ единиц в направлении, куда указывает её голова; «Направо $m$», где $m$ — целое число, вызывающая изменение направления движения на $m$ градусов по часовой стрелке.
Запись «Повтори $k$ [Команда1 Команда2 … Команда $S$]» означает, что последовательность из $S$ команд повторится $k$ раз, где $k$ — целое число.
Черепахе был дан для исполнения следующий алгоритм:
«Направо 315 Повтори 7 [Вперёд 16 Направо 45 Вперёд 8 Направо 135]».
Определите, сколько точек с целочисленными координатами будут находиться внутри области, которая ограничена линией, заданной алгоритмом. Точки на линии учитывать не следует.
Решение по шагам
4 шагаПосле команды «Направо 315» начальное направление движения задаётся углом 135 градусов относительно положительного направления оси абсцисс. Последовательно моделируем 7 повторений команд и получаем координаты всех вершин замкнутой ломаной.
По координатам вершин определяем минимальные и максимальные значения абсциссы и ординаты, то есть ограничивающий прямоугольник области.
Перебираем все точки с целочисленными координатами в этом прямоугольнике. Для каждой точки проверяем, находится ли она строго внутри построенной области; точки на границе не засчитываем.
Количество точек, прошедших проверку принадлежности внутренней области, равно 77.
Где здесь ошибаются
Учитывают точки, лежащие на границе.
Поворачивают Черепаху против часовой стрелки вместо поворота по часовой стрелке.
Проверяют только точки в вершинах ломаной, а не все целочисленные точки внутри ограничивающего прямоугольника.