Кластеризация звёзд

Задание 27 ЕГЭ-2026 по информатике · от первой диаграммы до досрочного 2026 с параметрами звёзд

На плоскости даны точки-звёзды. Их надо разбить на N непересекающихся кластеров (каждый помещается в прямоугольник H×W), для каждого найти центр-медоид и посчитать какую-то функцию от центров.

Медоид — ключевой термин

На станции КЕГЭ установлен LibreOffice Calc — это разрешённый инструмент. Кластеризацию делает не алгоритм, а твой глаз по точечной диаграмме. Python нужен только для медоида и подсчёта ответа.

Файл выглядит просто — в каждой строке координаты одной звезды через пробел, десятичный разделитель — запятая:

27_A.txt2,73 4,15
3,18 4,72
2,91 3,88
...

Чтобы получить из этих строк список пар чисел, нужно сделать 5 простых операций над каждой строкой. Сначала покажу развёрнутый вариант через обычный цикл — в нём видно, что происходит на каждом шаге:

развёрнутоpts = []                                # пустой список точек
with open('27_A.txt', encoding='utf-8') as f:
    for line in f:                     # шаг 1: читаем по строкам
        line = line.strip()             # шаг 2: убираем переносы '\n'
        if not line:                    #   и пропускаем пустые строки
            continue
        line = line.replace(',', '.')    # шаг 3: запятая → точка
        parts = line.split()            # шаг 4: '2.73 4.15' → ['2.73', '4.15']
        x = float(parts[0])            # шаг 5: строка → число
        y = float(parts[1])
        pts.append((x, y))              # кладём кортеж (x, y) в список

А теперь то же самое одной строкой через list comprehension. Идея ровно та же, просто записана компактнее:

компактноwith open('27_A.txt', encoding='utf-8') as f:
    pts = [tuple(map(float, l.replace(',', '.').split()))
           for l in f]

Что делает каждая часть компактной записи

А если в файле 3 столбца? (досрочный 2026)

В досрочном 2026 в каждой строке три значения: x y type. Тогда чтение совсем чуть-чуть длиннее:

3 столбцаstars = []
with open('27_A.txt', encoding='utf-8') as f:
    for line in f:
        line = line.strip().replace(',', '.')
        if not line: continue
        x, y, type_s = line.split()      # распаковка в 3 переменные
        stars.append((float(x), float(y), type_s))

Слева — таблица координат (как в файле 27_A.txt). Справа — диаграмма. Двигай ползунок — точки в реальном времени перекрашиваются. Включи кнопку «медоиды» — увидишь центры кластеров.

Попробуй: поставь границу на x = 1.5 — почти все точки в одном кластере. Правильное разделение — в районе x ≈ 5, где между облаками пустой зазор.

Для файла Б нужно три кластера — значит, две разделяющие прямые. Двигай оба ползунка.

В интерактивах ты видел кнопку «медоиды» — и центры кластеров действительно оказывались на одной из точек. Сейчас разберём, какой код это делает. Вот компактная запись функции:

компактноdef medoid(c):
    return min(c, key=lambda p: sum(dist(p, q) for q in c))

В одной строке тут спрятано четыре идеи: min, key, lambda и сумма расстояний. Разберём по очереди.

Что значит каждый кусок

То же самое через обычный цикл

Если min, key и lambda кажутся магией — вот тот же алгоритм через обычный цикл, без single-line магии. Делает ровно то же самое:

через циклdef medoid(c):
    best = c[0]                # лучшая точка (пока — первая)
    best_sum = 10**18           # минимальная сумма (пока — «бесконечность»)

    for p in c:               # перебираем все точки кластера
        s = 0                  # сумма расстояний от p до остальных
        for q in c:
            s = s + dist(p, q)
        
        if s < best_sum:       # нашли точку с меньшей суммой —
            best_sum = s       #   запомнили её
            best = p

    return best             # точка с минимальной суммой расстояний

Как это работает на примере

Пусть кластер из 4 точек: A=(0,0), B=(1,0), C=(2,0), D=(3,0). Считаем суммы расстояний от каждой точки до остальных:

Видим: точки B и C «равноправно центральные». min вернёт ту, которая встретилась первой. В реальной задаче ФИПИ гарантирует единственность медоида — такого равенства не будет.

Облака могут лежать не только слева-справа. Тогда нужно выбрать правильное направление разделителя. В интерактиве ниже: сверху выбираешь расположение данных, снизу — направление. Только одна комбинация работает для каждого расположения.

Когда облака стоят треугольником (одно сверху, два внизу), нужны две границы: одна горизонтальная для верхнего, одна вертикальная для нижних. Классическая L-образная конфигурация.

паттернif p[1] > 5:                        # y > 5 — верхнее облако
    c1.append(p)
elif p[0] < 5:                      # из оставшихся: x < 5 — левое нижнее
    c2.append(p)
else:                                # всё прочее — правое нижнее
    c3.append(p)

В части вариантов (ЕГЭ-2025, резервы) среди обычных точек прячутся выбросы — одинокие звёзды далеко от любого облака. На диаграмме они сразу заметны. Кликни по точке (или строке в таблице) — пометишь её как выброс. Она перестанет участвовать в медоиде.

В досрочном ЕГЭ-2026 (7 апреля 2026) в задание 27 добавили третий столбец — характеристику звезды, записанную слитно: цвет (буква) + светимость (цифра) + размер (римская цифра).

пример строки2,73 4,15 G2II
 |    |   |||
 x    y   цвет свет. размер
               G — белый, 2 — светимости 2, II — карлик
               # итого: белый карлик светимости 2

Таблица обозначений

x, y, type_s = line.replace(',', '.').split()
x, y = float(x), float(y)
color = type_s[0]      # 1-я буква — цвет, напр. 'G'
bright = type_s[1]     # 2-й символ — цифра, напр. '2'
size = type_s[2:]      # всё после — размер, напр. 'II'

Легенда цветов

Радиус точки отражает «размер» звезды: I (бланкет) — маленький, VII (пухляк) — большой.

Базовая задача: средние координат центров (досрочный 2025)

базовыйfrom math import dist

with open('27_A.txt', encoding='utf-8') as f:
    pts = [tuple(map(float, l.replace(',', '.').split()))
           for l in f if l.strip()]

c1 = [p for p in pts if p[0] < 5]   # условие с диаграммы
c2 = [p for p in pts if p[0] >= 5]

def medoid(c):
    return min(c, key=lambda p: sum(dist(p, q) for q in c))

cen1, cen2 = medoid(c1), medoid(c2)
Px = (cen1[0] + cen2[0]) / 2
Py = (cen1[1] + cen2[1]) / 2
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# Эталон файла A досрочного 2025: 167990 73043

Досрочный 2026: звёзды с параметрами (файл A)

досрочный'26from math import dist

stars = []
with open('27_A.txt', encoding='utf-8') as f:
    for line in f:
        line = line.strip().replace(',', '.')
        if not line: continue
        x, y, type_s = line.split()
        stars.append((float(x), float(y),
                      type_s[0], type_s[1], type_s[2:]))

c1 = [s for s in stars if s[1] > 10]    # верхнее облако
c2 = [s for s in stars if s[1] <= 10]   # нижнее облако

big = max([c1, c2], key=len)               # самый большой кластер

def medoid(c):
    return min(c, key=lambda p: sum(dist((p[0],p[1]),(q[0],q[1]))
                                  for q in c))

center = medoid(big)

# Расстояния от центра до «белых бланетов» (GI) — со всех точек!
dists = []
for s in stars:
    if s[2] == 'G' and s[4] == 'I':
        if (s[0], s[1]) != (center[0], center[1]):
            dists.append(dist((s[0],s[1]), (center[0],center[1])))

A1, A2 = min(dists), max(dists)
print(int(abs(A1 * 10000)), int(abs(A2 * 10000)))
# Эталон: 5522 75202