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

Решение:

После Направо 60 голова смотрит под углом $30^{\circ}$ к оси $Ox$. В цикле Вперёд 8 поднимает Черепаху в точку $(4\sqrt{3};\,4)$, Направо 120 разворачивает её вниз, Вперёд 4 возвращает на ось, а Направо 240 восстанавливает исходное направление. Значит каждый повтор рисует прямоугольный треугольник с катетами $4\sqrt{3}$ и 4 и гипотенузой 8, опирающийся на ось $Ox$; четыре зубца доводят Черепаху до точки $(16\sqrt{3};\,0)$.

Дальше Направо 120 направляет голову вниз, Вперёд 2 даёт $(16\sqrt{3};\,-2)$, Направо 90 и Вперёд $16\sqrt{3}$ — точку $(0;-2)$, а Направо 90 Вперёд 2 замыкает линию в начале координат.

Итак, фигура — прямоугольник $[0;\,16\sqrt{3}]\times[-2;\,0]$ с четырьмя треугольными зубцами сверху; $16\sqrt{3}\approx 27{,}71$. Фигура невыпуклая, поэтому в программе считаем методом луча и отдельно отбрасываем точки, лежащие на ломаной:

from math import sin, cos, radians, hypot

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

def F(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):
    global a
    a -= m

R(60)
for i in range(4):
    F(8); R(120); F(4); R(240)
R(120); F(2); R(90); F(16 * 3 ** 0.5); R(90); F(2)

def on_line(px, py):          # точка лежит на самой ломаной?
    for i in range(len(P) - 1):
        x1, y1 = P[i]; x2, y2 = P[i + 1]
        L = hypot(x2 - x1, y2 - y1)
        d = ((x2 - x1) * (py - y1) - (y2 - y1) * (px - x1)) / L
        if abs(d) < 1e-6 and min(x1, x2) - 1e-6 <= px <= max(x1, x2) + 1e-6 \
                         and min(y1, y2) - 1e-6 <= py <= max(y1, y2) + 1e-6:
            return True
    return False

def inside(px, py):           # луч вправо: чётность числа пересечений
    c = False
    for i in range(len(P) - 1):
        x1, y1 = P[i]; x2, y2 = P[i + 1]
        if (y1 > py) != (y2 > py):
            if x1 + (py - y1) * (x2 - x1) / (y2 - y1) > px:
                c = not c
    return c

xs = [p[0] for p in P]; ys = [p[1] for p in P]
print(sum(inside(px, py) and not on_line(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)))

Программа печатает 91. По строкам это: при $y=-1$ — 27 точек ($x=1,\dots,27$); при $y=0$ — тоже 27 (отрезок оси проходит внутри фигуры, а «впадины» $4\sqrt{3}$, $8\sqrt{3}$, $12\sqrt{3}$ не целые); при $y=1$ — 20, при $y=2$ — 12, при $y=3$ — 5. Итого $27+27+20+12+5=91$. Ответ: 91