Задание 6 ЕГЭ по информатике. Исполнитель Черепаха.

Подход A — через цвет пикселя (быстрый старт)

Идея: закрасить внутренность многоугольника цветом (например, red) и обойти сетку с шагом масштаба K, считывая цвет в координате. Если цвет равен red — точку учитываем. Такой метод прост и хорошо иллюстрирует идею, но может давать сбои при наложении сегментов/толстых линий и из-за особенностей Canvas.

Улучшенная версия «цветового» метода с ускорением

import turtle as t

def setup_fast():
    t.hideturtle(); t.speed(0); t.tracer(0, 0)

def get_color_at_canvas_xy(x, y):
    # Получаем tk.Canvas и смотрим верхний элемент под точкой (x,y)
    sc = t.getcanvas()
    items = sc.find_overlapping(x, y, x, y)
    if not items: 
        return None
    return sc.itemcget(items[-1], 'fill') or sc.itemcget(items[-1], 'outline')

def count_grid_points_by_color(xmin, xmax, ymin, ymax, K=10, target='red'):
    cnt = 0
    for ix in range(xmin, xmax + 1):
        for iy in range(ymin, ymax + 1):
            # tk.Canvas ось Y направлена вниз — инвертируем экранную Y
            col = get_color_at_canvas_xy(ix * K, -iy * K)
            if col == target:
                cnt += 1
    return cnt

# Пример использования:
# 1) рисуем и заливаем красным; 2) t.update(); 3) считаем
setup_fast()
K = 10
t.color('green', 'red')  # граница зелёная, внутренняя заливка красная
t.begin_fill()
t.left(90)
for _ in range(4):
    t.forward(10 * K)
    t.right(90)
t.end_fill()
t.update()

inside = count_grid_points_by_color(-50, 50, -50, 50, K=K, target='red')
print(inside)

Важный приём: если по условию нужно учитывать точки на границе, сделайте и линию, и заливку red: t.color('red', 'red'). Если не учитывать — задайте линии другой цвет: t.color('green', 'red'). Это устраняет двусмысленность при чтении цвета.

Подход B — геометрический (надёжно и очень быстро)

Вместо чтения пикселей используем математику: строим список вершин многоугольника из команд Черепахи и считаем точки внутри методом «луча» (ray casting). Преимущества — стабильность, отсутствие артефактов Canvas, скорость.

1) Как получить вершины многоугольника

Черепашка ходит по сетке в масштабе K. Мы можем не рисовать, а лишь «симулировать» её команды и собирать вершины в список.

import math

def simulate_turtle_path(commands, K=10, start=(0.0, 0.0), heading_deg=90.0):
    """
    commands: список шагов, например:
      [('fd', 10), ('rt', 120), ('rep', 7, [('fd', 10), ('rt', 120)])]
    Возвращает список вершин (x, y) в ПИКСЕЛЯХ экрана (как у turtle), 
    где ось Y направлена вверх (как в математике).
    """
    x, y = start
    ang = math.radians(heading_deg)
    verts = [(x, y)]
    def fd(n):
        nonlocal x, y
        x += K * n * math.cos(ang)
        y += K * n * math.sin(ang)
        verts.append((x, y))
    def rt(a):
        nonlocal ang
        ang -= math.radians(a)
    def lt(a):
        nonlocal ang
        ang += math.radians(a)
    def exec_list(lst):
        for cmd, *args in lst:
            if cmd == 'fd': fd(args[0])
            elif cmd == 'rt': rt(args[0])
            elif cmd == 'lt': lt(args[0])
            elif cmd == 'rep': 
                times, sub = args
                for _ in range(times): exec_list(sub)
            else:
                raise ValueError('unknown cmd', cmd)
    exec_list(commands)
    return verts

# пример для «Повтори 7 [Вперёд 10 Направо 120]»
commands = [('rep', 7, [('fd', 10), ('rt', 120)])]
V = simulate_turtle_path(commands, K=50)  # список вершин

2) Проверка «точка внутри многоугольника» (ray casting)

def point_in_poly(px, py, poly):
    """ Возвращает: 1 – внутри, 0 – снаружи, 2 – на границе. """
    inside = False
    on_edge = False
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1) % n]
        # проверка на ребро (точка лежит на отрезке)
        # векторное уравнение + допуск по коллинеарности
        dx, dy = x2 - x1, y2 - y1
        dxp, dyp = px - x1, py - y1
        cross = dx * dyp - dy * dxp
        if abs(cross) < 1e-9:
            dot = dxp * dx + dyp * dy
            if 0 - 1e-9 <= dot <= dx*dx + dy*dy + 1e-9:
                on_edge = True
                break
        # пересечение луча вправо с ребром
        condY = (y1 > py) != (y2 > py)
        if condY:
            x_int = x1 + dx * (py - y1) / (y2 - y1)
            if x_int > px:
                inside = not inside
    if on_edge: return 2
    return 1 if inside else 0

3) Подсчёт решётчатых точек в ограничивающем прямоугольнике

Считаем только целочисленные точки (с шагом масштаба K). Можно включать или исключать границу.

def count_lattice_points(poly, K=10, include_border=False):
    xs = [x for x, y in poly]; ys = [y for x, y in poly]
    xmin, xmax = int(min(xs) // K) - 1, int(max(xs) // K) + 1
    ymin, ymax = int(min(ys) // K) - 1, int(max(ys) // K) + 1
    total = 0
    for ix in range(xmin, xmax + 1):
        for iy in range(ymin, ymax + 1):
            px, py = ix * K, iy * K
            pos = point_in_poly(px, py, poly)
            if pos == 1 or (include_border and pos == 2):
                total += 1
    return total

# пример:
include_border = False  # или True — если по условию нужно учитывать точки на границе
ans = count_lattice_points(V, K=50, include_border=include_border)
print(ans)

Почему это быстрее и стабильнее: мы вообще не трогаем Canvas и цвета; работаем в чистой геометрии, ограничиваем перебор рамкой (bounding box), и за счёт этого код надёжно работает даже при сложных «накладывающихся» линиях или большой толщине пера.

Применяем к задачам из урока

Структура решения одинакова для всех пяти задач из презентации: формируем список команд (с повторами), получаем вершины simulate_turtle_path, затем считаем точки count_lattice_points. Если в условии «точки на линии учитывать/не учитывать», достаточно переключать include_border и/или подбирать цвет границы/заливки (в «цветовом» методе). Примеры исходных алгоритмов и разметка холста показаны в материалах урока.