Задание №6 — Анализ алгоритмов для исполнителя

#69347Задание №6ФИПИ

Анализ алгоритмов и исполнители

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке.
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз (где k – целое число).

Черепахе был дан для исполнения следующий алгоритм:
Направо 315 Повтори 11 [Вперёд 6 Направо 45].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, которая ограничена линией, заданной алгоритмом. Точки на линии учитывать не следует.

Правильный ответ

170

Пояснение

Решение:

Команда Направо 315 — это то же самое, что поворот налево на $45^\circ$ : голова Черепахи оказывается направленной под углом $135^\circ$ к оси абсцисс. Дальше каждый шаг — отрезок длины 6 и поворот на $45^\circ$ вправо, а восемь таких шагов дают полный оборот и замыкают правильный восьмиугольник со стороной 6. Итераций 11, то есть последние три отрезка ложатся поверх уже нарисованных сторон и фигуру не меняют.

Вершины восьмиугольника: $(0;0)$ , $(-3\sqrt2;\,3\sqrt2)$ , $(-3\sqrt2;\,3\sqrt2+6)$ , $(0;\,6\sqrt2+6)$ , $(6;\,6\sqrt2+6)$ , $(6+3\sqrt2;\,3\sqrt2+6)$ , $(6+3\sqrt2;\,3\sqrt2)$ , $(6;0)$ . Его площадь $2(1+\sqrt2)\cdot 6^2\approx 173{,}8$ , поэтому ответ должен быть чуть меньше 174. На границе лежат 15 целых точек: семь на нижней стороне от $(0;0)$ до $(6;0)$ и по четыре на двух наклонных сторонах, идущих под $45^\circ$ через узлы решётки, — их учитывать не нужно.

Остальные узлы переберём программой: восстанавливаем координаты вершин по алгоритму и проверяем каждый узел на принадлежность внутренности выпуклого многоугольника.

from math import cos, sin, radians

x = y = 0.0
h = 90.0
P = [(0.0, 0.0)]

def R(a):
    global h
    h -= a

def F(n):
    global x, y
    x += n * cos(radians(h))
    y += n * sin(radians(h))
    P.append((x, y))

R(315)
for _ in range(11):
    F(6)
    R(45)

poly = P[:8]             # восемь вершин восьмиугольника

def inside(px, py):
    d = []
    for i in range(8):
        ax, ay = poly[i]
        bx, by = poly[(i + 1) % 8]
        d.append((bx - ax) * (py - ay) - (by - ay) * (px - ax))
    return all(t > 1e-9 for t in d) or all(t < -1e-9 for t in d)

print(sum(inside(a, b) for a in range(-20, 25) for b in range(-20, 25)))

Программа выводит 170. Ответ: 170