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

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

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

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

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

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

206

Пояснение

Решение:

После команды Направо 60 голова Черепахи повёрнута на $30^\circ$ к оси абсцисс, а дальше каждый шаг — отрезок длины 9 и поворот ровно на $60^\circ$ в одну и ту же сторону. Шесть таких шагов дают полный оборот $6\cdot 60^\circ=360^\circ$ и замыкают правильный шестиугольник со стороной 9; седьмой шаг просто повторяет первую сторону и новой линии не добавляет.

Вершины шестиугольника: $(0;0)$ , $\left(\tfrac{9\sqrt3}{2};\,4{,}5\right)$ , $(9\sqrt3;\,0)$ , $(9\sqrt3;\,-9)$ , $\left(\tfrac{9\sqrt3}{2};\,-13{,}5\right)$ , $(0;\,-9)$ . Его площадь равна $\tfrac{3\sqrt3}{2}\cdot 9^2\approx 210{,}4$ , значит искомое число близко к 210. На границе лежат ровно 10 целых точек — весь левый вертикальный отрезок от $(0;-9)$ до $(0;0)$ ; по условию их учитывать не следует.

Точный подсчёт удобно доверить программе: воспроизводим ход Черепахи, берём первые шесть полученных вершин и для каждого узла решётки проверяем, что все векторные произведения сторон на векторы к этому узлу одного знака — это и означает «строго внутри выпуклого многоугольника».

from math import cos, sin, radians

x = y = 0.0
h = 90.0                 # голова смотрит вверх
P = [(0.0, 0.0)]

def R(a):                # Направо a
    global h
    h -= a

def F(n):                # Вперёд n
    global x, y
    x += n * cos(radians(h))
    y += n * sin(radians(h))
    P.append((x, y))

R(60)
for _ in range(7):
    F(9)
    R(60)

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

def inside(px, py):
    d = []
    for i in range(6):
        ax, ay = poly[i]
        bx, by = poly[(i + 1) % 6]
        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, 21) for b in range(-20, 21)))

Программа печатает 206. Ответ: 206