Задание №27. Кластеры и характеристики объектов

В файле записаны частицы: их координаты, скорости, массы и признаки. Требуется объединить частицы с близкими энергиями, выбрать центр каждой группы и вычислить две характеристики. Основная трудность состоит в том, что близость при разбиении и расстояние в ответе определяются по-разному. Энергия отвечает за состав групп и выбор центров, а координаты используются для поиска самой далёкой пары внутри группы.

Условие и входной файл

Основной пример — задание №27 из проекта демоверсии ФИПИ-2027. В карточке доступны полное условие и входной файл. Это проект документов. Пример содержит один файл demo_27.txt; ответ состоит из двух целых чисел в одной строке. Описание прежних вариантов с отдельными файлами А и Б не задаёт формат этого примера.

В каждой строке находятся шесть полей: координаты x,y, проекции скорости v_x,v_y, масса m и признак, записанный римскими цифрами от I до VII. Числовые значения даны в одинаковых для всех частиц единицах; придумывать названия этих единиц не требуется. Файл содержит 2604 строки без заголовка. Поэтому первая строка уже описывает частицу, а не количество записей.

По условию частицы образуют ровно четыре непустых непересекающихся кластера. Кластер здесь означает группу, в которой энергии любых двух частиц отличаются не более чем на R=2. Разбиение существует и единственно. Центр каждого кластера тоже единственен: это его частица с минимальной суммой модулей разностей энергий до остальных частиц группы.

После нахождения кластеров требуются две величины. Q_1 равна наибольшему евклидову расстоянию между двумя частицами признака II, принадлежащими одному кластеру. Q_2 равна максимальной энергии среди четырёх центров. В ответ записываются целые части этих величин после умножения каждой на 10000.

От строки файла к энергии

Кинетическая энергия вычисляется по массе и проекциям скорости:

E=\frac{m(v_x^2+v_y^2)}{2}.

Координаты в эту формулу не входят. Две частицы могут находиться далеко друг от друга, но иметь близкие энергии и попасть в один кластер. И наоборот, совпадение координат само по себе не означает близость энергий. Это позволяет сразу отделить поля, определяющие разбиение, от полей для последующего расчёта расстояния.

В иллюстрации официального условия у первой частицы проекции скорости равны 3 и -4, масса равна 0{,}2. Сумма квадратов проекций равна 9+16=25, поэтому E=0{,}2\cdot25/2=2{,}5. Отрицательная проекция не делает энергию отрицательной: она возводится в квадрат. Эти данные иллюстрируют формулу и не заменяют полный входной файл.

В исходном файле дробная часть отделена запятой. Перед преобразованием в float запятая заменяется точкой. Вызов split() без аргумента обрабатывает и несколько пробелов, и табуляцию. Первые пять полей становятся числами; последнее остаётся строкой. Для дальнейшей работы достаточно хранить запись (e, x, y, t): энергию, координаты и признак. Проекции скорости и масса уже выполнили свою роль в расчёте энергии.

Разбиение по минимальной энергии

После сортировки по энергии минимальное и максимальное значения каждой группы оказываются на её краях. Разность любых двух энергий не превосходит разности крайних. Поэтому требование ко всем парам равносильно одному условию:

E_{\max}-E_{\min}\le R.

Это условие относится к ширине всей группы. Проверка только соседних энергий его не заменяет. Например, учебная последовательность 1; 2{,}5; 4 имеет соседние разности 1{,}5, но разность крайних равна 3. При пороге 2 все три частицы нельзя объединить в один кластер.

Программа начинает группу с минимальной ещё не обработанной энергии. Эта энергия становится опорной и не меняется, пока группа строится. Очередная частица добавляется, если её энергия отличается от опорной не более чем на порог. При превышении порога создаётся следующая группа. Каждая частица обрабатывается один раз, а сортировка гарантирует, что более поздние энергии не окажутся меньше уже просмотренных.

Здесь требуется отдельная проверка применимости. Построенные группы непусты, не пересекаются, содержат все частицы и удовлетворяют ограничению ширины. На официальном файле их получается ровно четыре. Значит, программа построила допустимое разбиение из условия; по гарантии единственности это и есть искомые кластеры. Если такой проход даст другое количество групп на иных данных, считать ответ по ним нельзя. В программе предусмотрена явная остановка, а не молчаливое принятие неподходящего результата.

Полученные размеры групп по возрастанию энергии:

Сумма размеров равна числу строк входного файла. Это полезная проверка сохранности данных, но сама по себе она не доказывает правильность разбиения: дополнительно нужны ограничение ширины и правильное количество групп. Удалять необычные частицы как помехи нельзя: в данном условии все частицы участвуют в разбиении, исключения не предусмотрены.

На границе первой группы особенно заметна роль опоры. Её минимальная энергия приблизительно равна 1{,}200505, максимальная 3{,}099447. Их разность меньше двух. Следующая энергия приблизительно равна 4{,}400790: от предыдущей записи она отличается примерно на 1{,}301343, но от опоры уже больше чем на три. Поэтому начинается новая группа, хотя разрыв между соседями меньше порога. Приведённые значения округлены только для пояснения; программа сравнивает вычисленные энергии без такого сокращения.

Почему центр находится в середине

Для кандидата с энергией z требуется минимизировать сумму S(z)=\sum_i|z-E_i|. Здесь складываются разности энергий, а не расстояния между координатами. Включение самого кандидата в сумму ничего не меняет: его слагаемое равно нулю.

Минимум такой суммы достигается на медиане. Причину видно при мысленном перемещении кандидата по числовой прямой: пока справа больше значений, чем слева, движение вправо уменьшает суммарное расстояние. После перехода через середину больше значений остаётся слева, и дальнейшее движение начинает увеличивать сумму.

Например, для учебных энергий 2; 2{,}5; 3 суммы отклонений равны соответственно 1{,}5; 1; 1{,}5. Центр имеет энергию 2{,}5. Среднее арифметическое здесь случайно совпадает с медианой; причиной выбора остаётся минимум суммы модулей. На несимметричных данных среднее и медиана могут различаться.

В официальных группах количество частиц нечётно. Поскольку группы уже отсортированы, центральная запись доступна по индексу len(g)//2. При нумерации Python с нуля это и есть средняя позиция. Для произвольного чётного количества различных энергий две средние частицы дают одинаковую минимальную сумму, поэтому единственность нельзя предполагать без условия. Здесь она гарантирована и подтверждается исходными данными.

Так, первая группа содержит 501 частицу. Индекс центра равен 250: до него находятся двести пятьдесят записей и после него столько же. Это позиция после сортировки внутри группы, а не номер строки исходного файла. В файле та же частица записана в строке 1719. Сортировка переносит целую запись, поэтому координаты и признак остаются связаны с нужной энергией; сортировать каждый столбец независимо было бы ошибкой.

После выбора четырёх центров остаётся взять наибольшую их энергию. Она принадлежит центру четвёртого кластера и равна приблизительно 10{,}0704670276. Признак центра не обязан быть II: ограничение на признак относится к другой части задачи.

Самая далёкая пара нужного признака

В каждом уже построенном кластере отдельно отбираются частицы, у которых последнее поле точно равно 'II'. Для двух таких частиц с координатами (x_1,y_1) и (x_2,y_2) евклидово расстояние определяется формулой:

d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}.

Искомая пара может не включать центр. Поэтому программа перебирает все пары подходящих частиц внутри каждой группы. При фиксированном индексе i второй индекс проходит только предыдущие позиции: каждая неупорядоченная пара рассматривается один раз. Пары из разных кластеров не образуются, даже если их расстояние оказалось бы больше.

Список подходящих координат создаётся заново для очередного кластера. Общим остаётся только накопленный максимум: новый кластер может его увеличить или оставить прежним. Если в отдельной группе меньше двух подходящих частиц, она не создаёт ни одной допустимой пары и не меняет этот максимум.

Для выбора максимума достаточно сравнивать квадраты расстояний: квадратный корень сохраняет порядок неотрицательных чисел. В переменной dmax накапливается максимальный квадрат по всем группам, а корень извлекается один раз после перебора. Подмена расстояния квадратом безопасна именно для сравнения; перед получением ответа корень обязательно возвращается.

В кластерах официального файла признак II имеют соответственно 83, 86, 103, 118 частиц. Это даёт 19214 проверяемых пар. Максимум достигается в первом кластере; расстояние приблизительно равно 53{,}9936261401. Поиск центров и поиск пары используют одни группы, но разные критерии.

Небольшой учебный файл

Ниже приведены авторские сокращённые данные, а не строки полного файла ФИПИ. Они сохраняют определения энергии, центра и обеих характеристик. У всех частиц скорость имеет проекции 2 и 0, поэтому энергия равна удвоенной массе.

0 0 2 0 1 II
0 3 2 0 1,25 I
4 0 2 0 1,5 II
10 0 2 0 3 II
11 0 2 0 3,25 I
12 0 2 0 3,5 II
20 0 2 0 5 II
21 0 2 0 5,25 I
22 0 2 0 5,5 II
30 0 2 0 7 II
31 0 2 0 7,25 I
32 0 2 0 7,5 II

Энергии образуют группы (2; 2{,}5; 3), (6; 6{,}5; 7), (10; 10{,}5; 11) и (14; 14{,}5; 15). Ширина каждой равна единице, а между соседними группами разрыв равен трём. Поэтому ни одна пара из разных групп не удовлетворяет порогу, и разбиение на четыре кластера вынуждено.

Медианные энергии равны 2{,}5; 6{,}5; 10{,}5; 14{,}5, следовательно, Q_2=14{,}5. Все центры имеют признак I, что не мешает им быть центрами. В первой группе две частицы II имеют координаты (0,0) и (4,0); расстояние равно четырём. В остальных группах расстояния между частицами II равны двум. Получается Q_1=4, ответ учебного файла: 40000\quad145000.

Программа для полного файла

Файл demo_27.txt находится в рабочем каталоге программы. В списке p хранятся частицы, в c готовые группы, в q координаты частиц II текущей группы. Имя g обозначает текущую группу. В цикле for t in p переменная t содержит целую запись частицы; в цикле for e,x,y,t in g она получает только последний элемент записи — признак. Кортеж начинается с энергии, поэтому обычная сортировка ставит записи в нужный порядок. При совпадении энергий порядок остальных полей не влияет на ширину группы.

from math import sqrt

R, K = 2.0, 4
p = []
with open(
  'demo_27.txt',
  encoding='utf-8-sig'
) as f:
  for s in f:
    if not s.strip():
      continue
    s = s.replace(',', '.')
    a = s.split()
    x,y,vx,vy,m = map(
      float, a[:5])
    e = m*(vx*vx+vy*vy)/2
    p.append((e,x,y,a[5]))
p.sort()
c = []
for t in p:
  if not c or (
    t[0]-c[-1][0][0] > R):
    c.append([])
  c[-1].append(t)
if len(c) != K:
  raise ValueError('K')

dmax = emax = 0.0
for g in c:
  e = g[len(g)//2][0]
  emax = max(emax, e)
  q = []
  for e,x,y,t in g:
    if t == 'II':
      q.append((x,y))
  for i in range(len(q)):
    a,b = q[i]
    for j in range(i):
      x,y = q[j]
      d = ((a-x)**2
                 +(b-y)**2)
      dmax=max(dmax,d)
print(int(sqrt(dmax)*10000),
      int(emax*10000))

Выражение c[-1][0][0] выбирает энергию первой частицы последней группы. Именно она остаётся минимальной и служит опорой сравнения. Проверка количества групп стоит до поиска центров и расстояний. После неё emax хранит наибольшую энергию просмотренных центров, а dmax наибольший квадрат допустимого расстояния.

Сортировка требует O(N\log N) операций, где N означает количество частиц. Группировка и выбор центров после сортировки линейны. Если в кластере M частиц II, перебор рассматривает M(M-1)/2 пар. В худшем случае общая сложность квадратична. Небольшое фактическое число пар в демофайле не превращает этот алгоритм в линейный.

Ответ и контроль вычислений

Масштабирование выполняется после нахождения обеих характеристик. Для полного файла первое произведение приблизительно равно 539936{,}2614, второе 100704{,}6703. Отбрасывание дробной части даёт ответ 539936\quad100704. Обе величины неотрицательны, поэтому int выполняет требуемое усечение.

Ответ совпадает с ключом официального проекта. Дополнительно он проверен расчётом с точным представлением исходных десятичных чисел через целые: разбиение, минимумы сумм отклонений и максимальный квадрат расстояния дали тот же результат. Это существенно для последнего шага: округление до ближайшего целого изменило бы второе число. Промежуточное округление энергий также не нужно, поскольку оно меняет данные, по которым определяются группы и центры.

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

• Объединять цепочку близких соседей. В официальном примере по энергии соседние разрывы на границах кластеров меньше порога. Проверка только предыдущей частицы склеивает группы. Сравнение с минимумом текущей группы контролирует разность крайних и тем самым все пары.
• Строить группы по координатам или искать среднее. Такое решение заменяет заданные критерии другими. В данном условии разбиение и центр определяются энергией; средняя позиция нужна в отсортированном ряду энергий, а не на рисунке координат.
• Оставлять только II до выбора центра. Это меняет состав кластера и его медиану. Центр вычисляется по всем частицам; фильтр признака применяется только перед поиском пары. Сравнение признака должно быть точным: проверка вхождения 'II' в строку ошибочно захватывает III и VII.
• Искать расстояние от центра или между кластерами. Ни одна из этих величин не равна требуемому максимуму. Допустимая пара состоит из двух частиц II одной группы; все такие пары участвуют в сравнении.
• Округлять ответ. Функция round выбирает ближайшее целое, а условие требует целую часть произведения. Сначала вычисляется сама характеристика, затем применяется множитель, и только после него отбрасывается дробная часть.

В прежних задачах о координатных кластерах центр мог минимизировать сумму евклидовых расстояний. Для такого определения медиана энергий неприменима. Общими остаются этапы: установить правило группировки, отдельно прочитать определение центра, затем вычислить именно запрошенную характеристику. Конкретные формулы и ограничения определяются условием выбранной задачи.