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

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

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

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

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

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

Пояснение

Решение:

Посмотрим на суммарные повороты между соседними отрезками. Внутри первого цикла это $30^\circ+30^\circ=60^\circ$ , на стыке циклов — тоже $30^\circ+30^\circ=60^\circ$ , внутри второго цикла — $60^\circ$ . Значит, Черепаха рисует шесть отрезков длины 6 с одинаковым поворотом $60^\circ$ вправо: суммарный поворот $6\cdot 60^\circ=360^\circ$ , линия замыкается, и получается правильный шестиугольник со стороной 6.

Его вершины: $(0;0)$ , $(3;\,-3\sqrt3)$ , $(0;\,-6\sqrt3)$ , $(-6;\,-6\sqrt3)$ , $(-9;\,-3\sqrt3)$ , $(-6;0)$ , а площадь $\tfrac{3\sqrt3}{2}\cdot 6^2=54\sqrt3\approx 93{,}5$ . На границе лежат 7 целых точек — они все на горизонтальной стороне от $(-6;0)$ до $(0;0)$ , и по условию их учитывать не нужно.

Строго внутренние узлы пересчитаем перебором:

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(120)
for _ in range(3):
    R(30); F(6); R(30)
R(30)
for _ in range(3):
    F(6); 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, 20) for b in range(-20, 20)))

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