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

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

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

Если таких частиц в кластере несколько, центром считается частица с наибольшей координатой y.

В каждой строке текстового файла хранится информация об одной частице: координаты x и y, проекции вектора скорости V_x и V_y, масса m и признак.

Значения даны в одинаковых для всех частиц единицах измерения, обозначения единиц измерения в файле не приводятся.

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции.

Количество строк в файле не превышает 10 000.

Абсолютная величина каждого числового значения не превышает 100,0.

Известно, что все описанные в файле частицы подразделяются ровно на пять кластеров (K=5) с R=2,5 для каждого.

Для каждого кластера определите его центр, затем найдите два числа: Q1 — сумму модулей скоростей √(V_x²+V_y²) всех найденных центров кластеров и Q2 — наименьшее евклидово расстояние между двумя разными частицами одного кластера, имеющими признак III или V, при условии, что угол между их векторами скоростей превышает 90 градусов (скалярное произведение строго отрицательно: V_x1 · V_x2 + V_y1 · V_y2 < 0).

В ответе: целая часть Q1 × 10 000, затем целая часть Q2 × 10 000.

Для справки

Модуль момента импульса частицы массы m, находящейся в точке с координатами x и y и обладающей скоростью V⃗=(V_x;V_y), вычисляется по формуле:

L = m · |x · V_y - y · V_x|

Манхэттенское расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле:

d_M(A,B) = |x1 - x2| + |y1 - y2|

Евклидово расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле:

d(A,B)=√((x2 - x1)²+(y2 - y1)²)

Типовой пример организации данных во входном файле

Три строки файла для трёх частиц:

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 III

Для частицы из первой строки примера момент импульса L равен 0,748.

Типовой пример имеет иллюстративный характер.

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