№946819728
Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты, вектор скорости, масса, а также признак, характеризующий внутреннее строение частицы, обозначаемый числами от I до VII (в римской системе счисления).
Учёный решил провести кластеризацию частиц по значениям их кинетической энергии, то есть разбить их множество на K непересекающихся непустых подмножеств (кластеров), таких, что модуль разности кинетических энергий любых двух частиц каждого подмножества не превосходит значения R. Гарантируется, что такое разбиение существует и единственно для заданного R. Будем называть центром кластера такую его частицу, для которой сумма модулей разности кинетических энергий со всеми остальными частицами этого кластера минимальна. Для каждого кластера гарантируется единственность его центра.
В каждой строке текстового файла хранится информация об одной частице: координаты x и y, проекции вектора скорости Vx и Vy, масса m и признак. Значения даны в одинаковых для всех частиц единицах измерения, обозначения единиц измерения в файле не приводятся. Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10 000. Абсолютная величина каждого числового значения не превышает 100,0. Известно, что все описанные в файле частицы подразделяются ровно на 4 кластера (K = 4) с R = 2,0 для каждого.
Для каждого кластера определите его центр, затем найдите два числа: Q1 - наибольшее расстояние между центрами кластеров, и Q2 - среднее арифметическое энергий центров.
В ответе запишите два числа: сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.
Для справки
Кинетическая энергия E частицы массы m, обладающей скоростью v = (Vx; Vy), вычисляется по формуле E = ½ m (Vx2 + Vy2).
Евклидово расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)2 + (y2 − y1)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.
Типовой пример имеет иллюстративный характер. Чтобы выполнить это задание, используйте данные из прилагаемого файла.
Возможные данные иллюстрированы графиком (проекция частиц на плоскость координат).
График приведён для иллюстративных целей.