27_0160

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

Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты, вектор скорости, масса, а также признак, характеризующий внутреннее строение частицы, обозначаемый числами от I до VII (в римской системе счисления).

Учёный решил провести кластеризацию частиц по значениям их кинетической энергии, то есть разбить их множество на $K$ непересекающихся непустых подмножеств (кластеров), таких что модуль разности кинетических энергий любых двух частиц каждого подмножества не превосходит значения $R$. Гарантируется, что такое разбиение существует и единственно для заданного $R$.

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

В каждой строке текстового файла хранится информация об одной частице: координаты $x$ и $y$, проекции вектора скорости $V_x$ и $V_y$, масса $m$ и признак. Значения даны в одинаковых для всех частиц единицах измерения, обозначения единиц измерения в файле не приводятся. Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает $10\thinspace 000$. Абсолютная величина каждого числового значения не превышает $100{,}0$. Известно, что все описанные в файле частицы подразделяются ровно на $4$ кластера ($K = 4$) с $R = 2{,}0$ для каждого.

Для каждого кластера определите его центр, затем найдите два числа: $Q_1$ — наибольшее евклидово расстояние между частицами одного кластера, имеющими признак II, и $Q_2$ — максимальное значение кинетической энергии для центра кластера.

В ответе запишите два числа: сначала целую часть произведения $Q_1 \times 10\thinspace 000$, затем целую часть произведения $Q_2 \times 10\thinspace 000$.

Для справки

Кинетическая энергия $E$ частицы массы $m$, обладающей скоростью $\vec V = (V_x; V_y)$, вычисляется по формуле:

$$E = \tfrac{1}{2} m \left(V_x^2 + V_y^2\right).$$

Евклидово расстояние между двумя точками на плоскости $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле:

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

Типовой пример организации данных во входном файле. Три строки файла для трёх частиц

0,67    -2,14   3,0     -4,0    0,2     V
3,14    7,22    3,2     4,3     0,7     II
1,33    5,56    0,00    5,22    0,456   IV

Для частицы из первой строки примера кинетическая энергия равна $2{,}5$.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию:

• 27_0160.txt