Кластеры и характеристики объектов: конспект

В задании №27 из проекта демоверсии ФИПИ-2027 частицы делятся на четыре кластера по энергии. Центр определяется по всем частицам группы; самая далёкая пара выбирается только среди частиц II одного кластера.

Формулы и факты

Поля строки: координаты x,y, проекции скорости v_x,v_y, масса m, строковый признак. Файл demo_27.txt не имеет заголовка. Десятичная запятая заменяется точкой; split() обрабатывает пробелы и табуляцию.

При выборе центра z обозначает энергию кандидата, а E_i — энергии частиц группы.

• Энергия: E=m(v_x^2+v_y^2)/2.
• Ширина кластера: E_{\max}-E_{\min}\le2.
• Центр: частица с минимумом \sum_i|z-E_i|; энергия центра медианная.
• Квадрат расстояния: d^2=(x_2-x_1)^2+(y_2-y_1)^2.

Порядок вычислений

1. Для каждой частицы вычисляется энергия; вместе с ней сохраняются координаты и признак. Записи сортируются по энергии.
2. Группа начинается с минимальной оставшейся энергии. Следующие записи добавляются, пока отличаются от этого неизменного минимума не более чем на два. Затем начинается новая группа.
3. Проверяется количество групп: ровно четыре. Вместе с допустимой шириной и гарантией единственности это подтверждает искомое разбиение. Другое количество означает, что этим способом ответ ещё не получен.
4. В каждой отсортированной группе официального файла нечётное количество элементов; центр находится в g[len(g)//2]. Наибольшая энергия центров даёт Q_2. Признак центра может быть любым.
5. Внутри каждой группы отбираются записи с точным признаком 'II'. Перебираются все различные пары; сравниваются квадраты расстояний. Корень из общего максимума даёт Q_1.
6. Ответ: сначала int(Q1*10000), затем int(Q2*10000). Масштабирование и усечение выполняются в конце.

Возможные ловушки

• Близость соседей не ограничивает диаметр всей группы. Сравнение идёт с минимальной энергией, а не с предыдущей.
• Среднее координат или энергии не заменяет минимум суммы модулей. Медиана относится к ряду энергий; уникальность частицы-центра дана условием.
• Ранний фильтр II меняет центр. Фильтрация выполняется только для пары; поиск подстроки ошибочно захватывает III и VII.
• Расстояние до центра и расстояние между разными кластерами не подходят. Обе частицы допустимой пары имеют признак II и принадлежат одной группе.
• Округление меняет ответ. Для неотрицательных характеристик нужна целая часть после умножения; квадратный корень возвращается до масштабирования.

Перебор пар остаётся квадратичным в худшем случае. Быстрый выбор медианы не делает линейным весь алгоритм.