Задание 6 ЕГЭ: целые точки внутри одной фигуры

Черепаха: целые точки внутри фигуры. Тема номера — исполнитель черепаха. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке; Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.

Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм.

Вперёд 8 Направо 90 Вперёд 12 Направо 90 Вперёд 3 Налево 90
Вперёд 16 Направо 90 Вперёд 5 Направо 90 Вперёд 28

Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии следует учитывать.

Решение

Все повороты — на 90° (или кратны 90°), поэтому стороны идут вдоль осей и вершины фигуры целые: (0; 0), (0; 8), (12; 8), (12; 5), (28; 5), (28; 0).

Площадь фигуры S = 176 (разбиением на прямоугольники или по формуле Гаусса). На сторонах вдоль осей на каждую единицу длины приходится одна целая точка, поэтому на границе B = периметр = 72 точки.

По формуле Пика S = I + B/2 − 1, где I — число целых точек строго внутри. I = 176 − 72/2 + 1 = 141. С точками на линии: 141 + 72 = 213.

from math import cos, sin, radians, floor, ceil

def run(prog):
    # контуры нарисованных фигур: вершины до первого возвращения в начальную точку
    x = y = 0.0
    ang = 90                                   # голова вдоль оси ординат
    paths, cur = [], [(0.0, 0.0)]
    for cmd, n in prog:
        if cmd in ("fd", "bk"):
            d = n if cmd == "fd" else -n
            x += d * cos(radians(ang))
            y += d * sin(radians(ang))
            if cur is not None:
                cur.append((x, y))
        elif cmd == "rt":
            ang -= n
        elif cmd == "lt":
            ang += n
        elif cmd == "up":
            paths.append(cur)
            cur = None
        elif cmd == "down":
            cur = [(x, y)]
    if cur is not None:
        paths.append(cur)
    polys = []
    for f in paths:
        i = 1
        while abs(f[i][0] - f[0][0]) > 1e-6 or abs(f[i][1] - f[0][1]) > 1e-6:
            i += 1
        polys.append(f[:i])
    return polys

prog = ([("fd", 8), ("rt", 90), ("fd", 12), ("rt", 90), ("fd", 3), ("lt", 90)]
        + [("fd", 16), ("rt", 90), ("fd", 5), ("rt", 90), ("fd", 28)])

def on_line(poly, px, py):                     # точка лежит на одной из сторон
    for i in range(len(poly)):
        (x1, y1), (x2, y2) = poly[i - 1], poly[i]
        if abs((x2 - x1) * (py - y1) - (y2 - y1) * (px - x1)) < 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(poly, px, py):                      # луч вправо пересекает контур нечётное число раз
    res = False
    for i in range(len(poly)):
        (x1, y1), (x2, y2) = poly[i - 1], poly[i]
        if (y1 > py) != (y2 > py) and px < x1 + (py - y1) * (x2 - x1) / (y2 - y1):
            res = not res
    return res

poly = run(prog)[0]
xs = [q[0] for q in poly]
ys = [q[1] for q in poly]
count = 0
for x in range(floor(min(xs)) - 1, ceil(max(xs)) + 2):
    for y in range(floor(min(ys)) - 1, ceil(max(ys)) + 2):
        if on_line(poly, x, y):
            count += 1                     # точки на линии считаются
        elif inside(poly, x, y):
            count += 1
print(count)

Решить такую задачу — новый вариант с проверкой