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

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

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

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

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

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

101

Пояснение

Решение:

Сначала рисуется «подставка»: Направо 180 разворачивает Черепаху вниз, дальше $(0;0)\to(0;-2)\to(-30;-2)\to(-30;0)$ — это прямоугольник $30\times 2$ под осью $Ox$ .

После Направо 30 голова смотрит под углом $60^{\circ}$ к оси $Ox$ . В цикле Вперёд 5 Направо 120 Вперёд 5 Направо 240 Черепаха поднимается на 5 вверх-вправо и спускается на 5 вниз-вправо, снова оказываясь на оси: получается «зубец» — равносторонний треугольник со стороной 5 с основанием на оси $Ox$ . Шесть зубцов покрывают отрезок от $x=-30$ до $x=0$ , и линия замыкается.

Считаем целые точки строго внутри фигуры:

внутри прямоугольника: $x=-29,\dots,-1$ при $y=-1$ — 29 точек;
на отрезке $y=0$ (он проходит внутри фигуры): $x=-29,\dots,-1$ , кроме «впадин» $x=-25,-20,-15,-10,-5$ , лежащих на самой линии, — 24 точки;
внутри одного зубца (его высота $\tfrac{5\sqrt{3}}{2}\approx 4{,}33$ ): при $y=1$ — 4 точки, при $y=2$ — 2, при $y=3$ — 2, при $y=4$ — ни одной; итого 8, а на шесть зубцов — 48 точек.

$29+24+48=101$ . Фигура невыпуклая, поэтому в программе используем метод луча и отдельно отбрасываем точки, лежащие на ломаной:

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(180); F(2); R(90); F(30); R(90); F(2); R(30)
for i in range(6):
    F(5); R(120); F(5); R(240)

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

Ответ: 101