Кластеризация никуда не делась, но задача заметно изменилась.
Теперь вместо двух файлов работаем с одним, в котором для каждой частицы записаны сразу 6 характеристик:
x, y, Vx, Vy, m и признак от I до VII.
Причём кластеры теперь строятся не по координатам, а по кинетической энергии частиц. Всего кластеров 4, а максимальная разница энергий внутри каждого из них - R = 2.
При этом №27 по-прежнему оценивается максимум в 2 балла, а в ответ нужно получить два числа.
🩷Что происходит в программе на карточках?
Сначала считываем файл и для каждой частицы рассчитываем кинетическую энергию:
e = m * (vx 2 + vy 2) / 2
После этого сохраняем энергию, координаты и признак:
(e, x, y, t)
Остальные данные нам дальше уже не понадобятся.
Затем сортируем все частицы по энергии и формируем кластеры. Пока разница между энергией текущей частицы и первой частицы кластера не превышает 2, они относятся к одному кластеру. Как только разница становится больше - начинаем следующий.
В результате получаем те самые 4 кластера из условия.
Дальше считаем два ответа.
Q₂ - максимальная энергия центра кластера.
Центром считается частица, у которой сумма разностей энергий со всеми остальными минимальна. После сортировки таким элементом будет медиана, поэтому центр каждого кластера можно получить очень компактно:
center = cluster[len(cluster) // 2]
Остаётся выбрать максимальную энергию среди четырёх центров.
Q₁ - максимальное расстояние между частицами с признаком II внутри одного кластера.
Для каждого кластера оставляем только нужные точки:
if t == "II":
перебираем их попарно и считаем обычное евклидово расстояние по координатам x и y. Из всех полученных расстояний сохраняем максимальное.
В конце не забываем про формат ответа:
print(int(q1 * 10000),
int(q2 * 10000))
Для файла из демоверсии получаем:
539936 100704 ✅
Получается, новый №27 можно свести к довольно понятной цепочке:
посчитать энергию → отсортировать → разбить на кластеры → найти Q₁ и Q₂.
Так что огромное условие на две страницы выглядит страшнее, чем сама программа..
Сохраняйте карточки - здесь уже готовое решение нового прототипа №27 😎