27_0165

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

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

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

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

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

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

В ответе запишите два числа: сначала целую часть произведения $Q_1 \times 10,000$, затем целую часть произведения $Q_2 \times 10,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_0165.txt