Каталог: Задание №27. Анализ больших данных (Кластеризация / Префиксные суммы)

Банк задач: 124 Формат ЕГЭ 2026 Высокий (2 балла) 15-25 мин Шаблоны решений на Python

Выберите номер задания ЕГЭ:

№1 №2 №3 №4 №5 №6 №7 №8 №9 №10 №11 №12 №13 №14 №15 №16 №17 №18 №19 №20 №21 №22 №23 №24 №25 №26 №27

Спецификация и суть задания №27

Тема кодификатора Кластеризация точек методом k-средних / DBSCAN, поиск центроидов кластеров и кольцевая автодорога

Сложность и баллы Высокий (2 балла)

Рекомендуемое время 15-25 мин

Инструменты решения Python 3, open('27A.txt'), math.dist(p1, p2), Кластеризация по расстоянию, Префиксные суммы

Финальное и самое престижное задание ЕГЭ (2 первичных балла). Состоит из двух файлов: Файл A (маленький, до 1 000 строк) и Файл B (огромный, до 100 000 строк). В актуальных вариантах 2024–2026 годов 95% задач — это кластеризация точек на плоскости и нахождение центроидов.

Основные прототипы и разновидности

Тип 1: Кластеризация точек на плоскости и нахождение центроидов (Хит 2024–2026)

Разделение точек на 2–3 кластера по координатным границам или расстоянию и нахождение центроида каждого кластера.

Тип 2: Кластеризация с шумовыми точками (DBSCAN)

Фильтрация изолированных точек-выбросов, у которых нет соседей в заданном радиусе R.

Тип 3: Кольцевая автодорога и биолаборатории (Префиксные суммы)

Кольцевой массив с подсчетом стоимости доставки биоматериалов за O(N) через префиксные суммы.

Тип 4: Поиск пар / троек с делимостью расстояния на K

Динамический массив остатков для поиска максимального произведения элементов.

Теоретический фундамент и алгоритмы

1. Что такое Центроид кластера:

Центроид кластера — это точка кластера, сумма евклидовых расстояний от которой до всех остальных точек этого же кластера минимальна.

КРИТИЧЕСКИ ВАЖНО: Центроид — это реальная точка из файла, а не среднее арифметическое координат!
Евклидово расстояние между точками $(x_1, y_1)$ и $(x_2, y_2)$: math.dist(p1, p2) или ((x1-x2)**2 + (y1-y2)**2)**0.5.

2. Пошаговый алгоритм решения (Кластеризация):

Считываем координаты точек из файла, заменяя запятые на точки: coords = [float(x) for x in line.replace(',', '.').split()].
Разделяем точки на кластеры (по координатным границам $x, y$ или по расстоянию $< R$).

Для каждого кластера находим точку с минимальной суммой расстояний:

def get_centroid(cluster):
    best_pt = None
    min_dist = float('inf')
    for p1 in cluster:
        d_sum = sum(math.dist(p1, p2) for p2 in cluster)
        if d_sum < min_dist:
            min_dist = d_sum
            best_pt = p1
    return best_pt

Вычисляем координаты специальной точки $P$ (например, среднее арифметическое центроидов) и умножаем на 10 000 с отсечением дробной части: int(px * 10000), int(py * 10000).

Лайфхаки и фишки для ускорения

Совет

Функция math.dist(p1, p2) встроена в Python 3.8+ и работает быстрее ручного подсчета корня!

Совет

Для быстрого визуального разделения точек на кластеры посмотрите минимальные и максимальные X и Y в выборке.

Частые ошибки и экзаменационные ловушки

Ошибка: Взять среднее арифметическое координат вместо реального центроида
Центроид в ЕГЭ ОБЯЗАН быть одной из точек входного массива!

Правильно: Центроид находится только перебором точек кластера: min(sum(dist)).

Ошибка: Забыть заменить запятую на точку в float(line)
Файлы ЕГЭ часто содержат координаты с запятыми ('12,34 56,78') -> ValueError!

Правильно: Всегда делать line.replace(',', '.').split().

ГРОБ №27: Кластеры сложной формы с шумовыми выбросами

В файле B присутствуют отдельные точки-выбросы между кластерами.

Алгоритм решения: Фильтруйте изолированные точки: оставляйте только те точки, у которых в радиусе $R$ есть хотя бы $K$ соседей.

Практические задачи из банка КИМ (Всего: 124)

Решать в песочнице СмартКИМ

Задача #9033 №27 ЕГЭ