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

Решение:

Хвост поднят, поэтому Вперёд 100 Направо 90 Вперёд 100 только переводит Черепаху в точку $(100;100)$. После Направо 45 голова смотрит под углом $-45^{\circ}$ к оси $Ox$, и хвост опускается.

Цикл замыкается за два повтора: рисуется прямоугольник $20\times 30$, повёрнутый на $45^{\circ}$, с вершинами $(100;100)$, $(100+10\sqrt{2};\,100-10\sqrt{2})$, $(100-5\sqrt{2};\,100-25\sqrt{2})$, $(100-15\sqrt{2};\,100-15\sqrt{2})$.

Все стороны имеют угловые коэффициенты $\pm 1$, поэтому в переменных $s=x+y$ и $d=x-y$ условие «строго внутри» становится совсем простым:

$$200-30\sqrt{2}\lt s\lt 200,\qquad 0\lt d\lt 20\sqrt{2}.$$

Так как $30\sqrt{2}\approx 42{,}43$ и $20\sqrt{2}\approx 28{,}28$, подходят целые $s=158,159,\dots,199$ (42 значения) и $d=1,2,\dots,28$ (28 значений).

Пара $(s;d)$ отвечает целой точке $x=\dfrac{s+d}{2}$, $y=\dfrac{s-d}{2}$ тогда и только тогда, когда $s$ и $d$ одной чётности. Среди значений $s$ — 21 чётное и 21 нечётное, среди значений $d$ — 14 чётных и 14 нечётных.

Итого $21\cdot 14+21\cdot 14=588$. Проверим программой:

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

F(100); R(90); F(100); R(45)  # хвост поднят - это не рисуется
P = [(x, y)]                  # опустили хвост
for i in range(2):            # прямоугольник замыкается за 2 повторения
    F(20); R(90); F(30); R(90)

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)))

Ответ: 588