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

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

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

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

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

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

140

Пояснение

Решение:

Проследим направления. Черепаха рисует шесть отрезков длиной 7, 7, 6, 7, 7 и 20. Второй, третий и четвёртый отрезки идут в одном и том же направлении: перед Вперёд 6 суммарный поворот равен $60^\circ+300^\circ=360^\circ$ , то есть направление не меняется, а во втором цикле шаг делается до поворота. Поэтому они склеиваются в одну сторону длины $7+6+7=20$ . Между оставшимися четырьмя сторонами повороты по $90^\circ$ , и последний отрезок длины 20 приводит Черепаху точно в начало координат.

Получился прямоугольник со сторонами 7 и 20 с вершинами $(0;0)$ , $\left(-3{,}5;\,-\tfrac{7\sqrt3}{2}\right)$ , $\left(-3{,}5-10\sqrt3;\,10-\tfrac{7\sqrt3}{2}\right)$ , $(-10\sqrt3;\,10)$ — приближённо $(0;0)$ , $(-3{,}5;\,-6{,}06)$ , $(-20{,}82;\,3{,}94)$ , $(-17{,}32;\,10)$ .

Его площадь $7\cdot 20=140$ . Всего целых точек в прямоугольнике вместе с границей 142, но две из них — $(0;0)$ и $(-14;0)$ — лежат на сторонах и по условию не считаются. Остаётся $142-2=140$ .

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(180)
for _ in range(2):
    R(30); F(7); R(60)
R(300); F(6)
for _ in range(2):
    F(7); R(90)
F(20)

poly = [P[0], P[1], P[4], P[5]]      # вершины прямоугольника 7 x 20

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

Программа подтверждает: 140. Ответ: 140