Задание 6: Определение результатов работы простейших алгоритмов

Стандартная формулировка описывает исполнителя Черепаха: он стоит в начале координат, смотрит вдоль оси $Oy$, умеет выполнять команды «Вперёд $n$» (сдвиг на $n$ единиц в текущем направлении) и «Направо $m$» (поворот по часовой стрелке на $m$ градусов), а конструкция «Повтори $k$ [...]» повторяет блок команд $k$ раз. Дальше приводится конкретная программа, и требуется определить число точек с целочисленными координатами внутри области, ограниченной построенной линией, или внутри и на границе одновременно. Задание относится к базовому уровню сложности, оценивается в 1 первичный балл, на его реше …

• Направление движения задаётся углом $\theta$ относительно оси $Ox$; поворот «Направо $m$» уменьшает угол на $m$: $\theta_{new} = \theta_{old} - m$; поворот «Налево $m$» увеличивает угол на $m$.
• Переход к смещению по осям при движении «Вперёд $n$» в направлении $\theta$: $\Delta x = n\cos\theta,\ \Delta y = n\sin\theta$.
• Ломаная линия из цикла «Повтори $k$» замкнётся в правильный (возможно, звёздчатый) многоугольник только тогда, когда суммарный угол поворота кратен $360°$: $k\cdot m = 360°\cdot d$ для некоторого целого $d$.
• Если $d\ge 2$, вычерчивается звёздчатый многоугольник вида $\{k/d\}$; если $d=1$ — обычный выпуклый правильный $k$-угольник.
• Площадь многоугольника по координатам вершин (формула «шнурков», формула Гаусса): $S=\dfrac12\left|\sum_{i=1}^{n}\left(x_i y_{i+1}-x_{i+1} y_i\right)\right|$.
• Теорема Пика для многоугольника с вершинами в целочисленных точках: $S = I + \dfrac{B}{2} - 1$, где $I$ — число внутренних целых точек, $B$ — число целых точек на границе.
• Для прямоугольника со сторонами $a$ и $b$ (целые, стороны параллельны осям): число целых точек строго внутри равно $(a-1)(b-1)$; число целых точек внутри и на границе равно $(a+1)(b+1)$.
• Число целых точек на отрезке между целыми точками $(x_1,y_1)$ и $(x_2,y_2)$, включая концы, равно $\gcd(|x_2-x_1|,|y_2-y_1|)+1$.

1. Зафиксировать стартовую точку $(0,0)$ и стартовое направление (обычно вдоль $Oy$, угол $90°$).
2. Пошагово применить команды «Вперёд»/«Направо» (или «Налево»), вычисляя координаты каждой новой точки.
3. Проверить, не повторяется ли контур раньше окончания цикла: сравнить текущее положение и направление с начальными.
4. Определить тип получившейся фигуры (прямоугольник, правильный или звёздчатый многоугольник) и выписать координаты всех различных вершин.
5. Выбрать метод подсчёта: готовая формула для прямоугольника, теорема Пика для многоугольника с целыми вершинами, либо перебор по столбцам, если вершины нецелые.
6. Внимательно прочитать вопрос: считать нужно точки строго внутри, или внутри и на границе.
7. Выполнить вычисления и проверить результат прикидкой — сравнить полученное число с приближённой площадью фигуры (они должны быть близки).