Задание 6 ЕГЭ по информатике на Python: черепаха и точки внутри фигуры

В задании 6 ЕГЭ по информатике исполнитель Черепаха рисует фигуру по программе, а спрашивают, сколько точек с целыми координатами окажется внутри неё. Когда стороны идут не по клеткам, точки у наклонной линии глазами не разобрать: одна чуть внутри, соседняя чуть снаружи. На Python решение в два шага: черепаха из модуля turtle рисует фигуру с сеткой точек, а программа считает их сама. Примеры ниже запускаются прямо на странице, рисунок появляется под кодом. Пример задачи составлен для этой статьи, на экзамене фигура будет другой, а код — тот же.

ЕГЭ / 01koddo

Команды Черепахи на языке turtle

Пример задачи

Исполнитель Черепаха выполнил программу Повтори 3 [Вперёд 15 Направо 120]. Определи, сколько точек с целыми координатами находится внутри области, ограниченной получившейся линией. Точки на линии учитывать не следует.

Шаг 1: нарисовать фигуру и сетку

from turtle import *

tracer(0)
k = 20
left(90)
for i in range(3):
    forward(15 * k)
    right(120)
up()
for x in range(-1, 15):
    for y in range(-1, 17):
        goto(x * k, y * k)
        dot(3)
update()

Получился треугольник: левая сторона идёт вверх по оси, две другие — под углом. tracer(0) выключает анимацию, update() показывает готовый рисунок, а up() поднимает хвост, чтобы между точками сетки не было линий. Посмотри на точки у наклонных сторон: многие почти касаются линии, и сказать на глаз, внутри они или снаружи, трудно. Поэтому считать лучше программой.

Шаг 2: где углы фигуры

Черепаха помнит, где стоит: pos() возвращает координаты, heading() — направление. Пройдём программу с шагом 1 и запишем углы:

from turtle import *

left(90)
print(pos(), heading())
forward(15)
right(120)
print(pos(), heading())
forward(15)
print(pos())

(0.00,0.00) 90.0
(0.00,15.00) 330.0
(12.99,7.50)

Третий угол — (12.99, 7.50): координата не целая, поэтому на наклонных сторонах целых точек почти нет, и глазами их легко перепутать.

Шаг 3: посчитать точки программой

Соберём углы в список и проверим каждую целую точку вокруг фигуры: лежит ли она на линии, а если нет — внутри ли.

from turtle import *

tracer(0)
left(90)
corners = [pos()]
for i in range(3):
    forward(15)
    right(120)
    corners.append(pos())
edges = list(zip(corners, corners[1:]))

def between(v, a, b):
    return min(a, b) - 1e-9 <= v <= max(a, b) + 1e-9

def on_line(x, y):
    for (x1, y1), (x2, y2) in edges:
        cross = (x2 - x1) * (y - y1) - (y2 - y1) * (x - x1)
        if abs(cross) < 1e-9 and between(x, x1, x2) and between(y, y1, y2):
            return True
    return False

def inside(x, y):
    result = False
    for (x1, y1), (x2, y2) in edges:
        if (y1 > y) != (y2 > y) and x < x1 + (y - y1) * (x2 - x1) / (y2 - y1):
            result = not result
    return result

strict, line = 0, 0
for x in range(-20, 21):
    for y in range(-20, 21):
        if on_line(x, y):
            line += 1
        elif inside(x, y):
            strict += 1
print("внутри:", strict, "на линии:", line)

внутри: 90 на линии: 16

По условию точки на линии не считаются, поэтому ответ — 90. Если бы их нужно было учесть, ответ был бы 90 + 16 = 106.

• corners — углы фигуры в порядке обхода; последний совпадает с первым, так что edges — все три стороны.
• on_line проверяет, лежит ли точка на стороне: векторное произведение cross равно нулю, а сама точка — между концами стороны.
• inside — проверка лучом: из точки вправо проводится луч и считается, сколько сторон он пересечёт. Нечётное число — точка внутри, чётное — снаружи.
• 1e-9 — допуск на неточность дробных чисел: 12.99 из шага 2 на самом деле 12.990381…, и сравнивать такие координаты строгим == нельзя.
• range(-20, 21) перебирает квадрат с запасом вокруг фигуры. Если фигура больше, расширь диапазон: точка за его краем просто не будет посчитана.

Частые ошибки

Точки на линии. Условие всегда говорит, учитывать ли их, а ответы различаются: здесь 90 и 106. Программа печатает оба числа — бери то, о котором спрашивают.

Нет масштаба на рисунке. Без k сторона в 15 шагов — это 15 пикселей, и сетка слипается в пятно. Для подсчёта программой масштаб не нужен, а для рисунка — нужен.

Строгое сравнение дробей. Проверка cross == 0 вместо допуска пропускает точки, которые лежат на наклонной стороне. Например, черепаха стоит в точке (0, 10) и смотрит вверх; после right(135) и forward(10 * 2 ** 0.5) она проходит под 45° до (10, 0), и точка (5, 5) лежит ровно на этой стороне. Но из-за округления произведение для неё получается не нулём, а 7.1e-15.

Нет tracer(0) на компьютере. Сотни точек сетки черепаха будет рисовать по одной, и это долго. С tracer(0) и update() рисунок появится сразу.

Команды черепахи с рисунками — в статье «Черепаха в Python». Для больших фигур открой песочницу Python: там у программы больше времени, а рисунок можно сохранить. Задание 2 о таблицах истинности разобрано в статье «Задание 2 ЕГЭ на Python», а какие ещё задания решают программой — в статье «Python для ЕГЭ по информатике».