Высокий (2 балла)
Время: 15-25 мин
Python 3
open('27A.txt')
math.dist(p1, p2)
Кластеризация по расстоянию
Префиксные суммы
Все задачи №{ topic_num } в каталоге
Задание №27. Анализ больших данных (Кластеризация / Префиксные суммы)
Тема: Кластеризация точек методом k-средних / DBSCAN, поиск центроидов кластеров и кольцевая автодорога
Финальное и самое престижное задание ЕГЭ (2 первичных балла). Состоит из двух файлов: Файл A (маленький, до 1 000 строк) и Файл B (огромный, до 100 000 строк). В актуальных вариантах 2024–2026 годов 95% задач — это кластеризация точек на плоскости и нахождение центроидов.
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).
Разновидности и прототипы задания на экзамене
Тип 1: Кластеризация точек на плоскости и нахождение центроидов (Хит 2024–2026)
Разделение точек на 2–3 кластера по координатным границам или расстоянию и нахождение центроида каждого кластера.
Тип 2: Кластеризация с шумовыми точками (DBSCAN)
Фильтрация изолированных точек-выбросов, у которых нет соседей в заданном радиусе R.
Тип 3: Кольцевая автодорога и биолаборатории (Префиксные суммы)
Кольцевой массив с подсчетом стоимости доставки биоматериалов за O(N) через префиксные суммы.
Тип 4: Поиск пар / троек с делимостью расстояния на K
Динамический массив остатков для поиска максимального произведения элементов.
Боевой шаблон решения на Python
Запустить код в онлайн-песочнице# === Универсальный боевой шаблон Задания №27 (Кластеризация) ===
import math
# 1. Читаем точки из файла (27A.txt или 27B.txt):
points = []
with open('27_A.txt') as f:
for line in f:
parts = line.replace(',', '.').split()
if len(parts) == 2:
points.append((float(parts[0]), float(parts[1])))
# 2. Разделение на кластеры (пример для 2 кластеров по границе y = 3.0):
cluster1 = [p for p in points if p[1] > 3.0]
cluster2 = [p for p in points if p[1] <= 3.0]
# 3. Функция поиска реального центроида кластера:
def find_centroid(cluster):
best_p = None
min_sum = float('inf')
for p1 in cluster:
current_sum = sum(math.dist(p1, p2) for p2 in cluster)
if current_sum < min_sum:
min_sum = current_sum
best_p = p1
return best_p
c1 = find_centroid(cluster1)
c2 = find_centroid(cluster2)
print("Центроид кластера 1:", c1)
print("Центроид кластера 2:", c2)
# 4. Вычисление итогового ответа (Px * 10000, Py * 10000):
px = (c1[0] + c2[0]) / 2
py = (c1[1] + c2[1]) / 2
print("Ответ X:", int(px * 10000), "Ответ Y:", int(py * 10000))Анти-примеры (Типичные ошибки vs Как делать правильно)
Как делать НЕ надо:
Ошибка: Взять среднее арифметическое координат вместо реального центроида
Центроид в ЕГЭ ОБЯЗАН быть одной из точек входного массива!Как делать ПРАВИЛЬНО:
Правильно: Центроид находится только перебором точек кластера: min(sum(dist)).Как делать НЕ надо:
Ошибка: Забыть заменить запятую на точку в float(line)
Файлы ЕГЭ часто содержат координаты с запятыми ('12,34 56,78') -> ValueError!Как делать ПРАВИЛЬНО:
Правильно: Всегда делать line.replace(',', '.').split().
ГРОБ
ГРОБ №27: Кластеры сложной формы с шумовыми выбросами
В файле B присутствуют отдельные точки-выбросы между кластерами.
Как обойти ловушку: Фильтруйте изолированные точки: оставляйте только те точки, у которых в радиусе $R$ есть хотя бы $K$ соседей.
Лайфхаки и подводные камни на экзамене:
- Функция `math.dist(p1, p2)` встроена в Python 3.8+ и работает быстрее ручного подсчета корня!
- Для быстрого визуального разделения точек на кластеры посмотрите минимальные и максимальные X и Y в выборке.