Задание 27 ЕГЭ: кластеризация по энергии частиц

Кластеризация частиц по вычисляемой величине (энергии). Тема номера — кластеризация данных. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции скорости Vx и Vy, масса m и признак — римское число от I до VII. Частицы разбиваются на кластеры по значению кинетической энергии: в каждом кластере модуль разности энергий любых двух частиц не превосходит R = 3,0, а частицы разных кластеров отличаются по энергии больше чем на R. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла 27.txt записаны x, y, Vx, Vy, m и признак одной частицы, значения разделены пробелами, дробная часть отделяется запятой. Известно, что кластеров ровно 5.

Найдите два числа: Q1 — максимальное значение кинетической энергии среди центров кластеров; Q2 — наибольшее евклидово расстояние между частицами одного кластера, имеющими признак I. В ответе запишите сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.

Кинетическая энергия частицы массы m со скоростью (Vx; Vy): E = ½ · m · (Vx² + Vy²).

Скачать файл к примеру

Решение

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

Ответ: 330258 545254.

parts = []
for line in open('27.txt'):
    x, y, vx, vy, m, tag = line.replace(',', '.').split()
    x, y, vx, vy, m = map(float, (x, y, vx, vy, m))
    parts.append((m * (vx ** 2 + vy ** 2) / 2, x, y, tag))
parts.sort()
# режем по 4 наибольшим промежуткам между соседними энергиями
gaps = sorted(range(1, len(parts)), key=lambda i: parts[i][0] - parts[i - 1][0])
cuts = [0] + sorted(gaps[-4:]) + [len(parts)]
clusters = [parts[a:b] for a, b in zip(cuts, cuts[1:])]
centers = [c[len(c) // 2][0] for c in clusters]   # медиана: минимум суммы |Ei − Ej|
q1 = max(centers)
q2 = max(((a[1] - b[1]) ** 2 + (a[2] - b[2]) ** 2) ** 0.5
         for c in clusters for a in c for b in c if a[3] == b[3] == 'I')
print(int(q1 * 10000), int(q2 * 10000))

Решить такую задачу — новый вариант с проверкой