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

Решение:

Команда Направо 60 выполняется 18 раз, суммарный поворот равен $18\cdot 60^{\circ}=1080^{\circ}$ — это три полных оборота. Значит Черепаха трижды обводит один и тот же контур, а замыкается он уже за 6 команд: внешний угол $60^{\circ}$ — признак правильного шестиугольника со стороной 19.

Стартуя из $(0;0)$ головой вдоль оси $Oy$, получаем вершины $(0;0)$, $(0;19)$, $\left(\tfrac{19\sqrt{3}}{2};\,28{,}5\right)$, $(19\sqrt{3};\,19)$, $(19\sqrt{3};\,0)$, $\left(\tfrac{19\sqrt{3}}{2};\,-9{,}5\right)$.

Шестиугольник выпуклый и обходится по часовой стрелке, поэтому точка лежит строго внутри тогда и только тогда, когда для каждой стороны косое произведение $(x_2-x_1)(y-y_1)-(y_2-y_1)(x-x_1)$ отрицательно; равенство нулю означает, что точка лежит на самой линии, — такие точки не считаем.

from math import sin, cos, radians

P = [(0.0, 0.0)]
x = y = 0.0
a = 90.0                      # голова смотрит вдоль оси Oy

def F(n):                     # Вперёд n
    global x, y
    x = round(x + n * cos(radians(a)), 9)   # round убирает шум float
    y = round(y + n * sin(radians(a)), 9)
    P.append((x, y))

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

for i in range(6):            # шестиугольник замыкается за 6 команд
    F(19); R(60)

def inside(px, py):           # фигура выпуклая, обход по часовой стрелке
    for i in range(len(P) - 1):
        x1, y1 = P[i]; x2, y2 = P[i + 1]
        if (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1) >= -1e-9:
            return False      # точка на линии или снаружи
    return True

xs = [p[0] for p in P]; ys = [p[1] for p in P]
print(sum(inside(px, py)
          for px in range(int(min(xs)) - 1, int(max(xs)) + 2)
          for py in range(int(min(ys)) - 1, int(max(ys)) + 2)))

Программа печатает 922. Для контроля: площадь шестиугольника равна $\tfrac{3\sqrt{3}}{2}\cdot 19^{2}\approx 937{,}9$, а на линии лежат 20 целых точек (весь отрезок $x=0$, $0\le y\le 19$). Ответ: 922