Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты, вектор скорости, масса, а также признак, характеризующий внутреннее строение частицы, обозначаемый числами от I до VII (в римской системе счисления).
Учёный решил провести кластеризацию частиц по значениям модуля их момента импульса относительно начала координат, то есть разбить их множество на K непересекающихся непустых подмножеств (кластеров), таких, что модуль разности моментов импульса любых двух частиц каждого подмножества не превосходит значения R. Гарантируется, что такое разбиение существует и единственно для заданного R.
Будем называть центром кластера такую его частицу, для которой сумма Манхэттенских расстояний до всех остальных частиц этого же кластера минимальна.
Если таких частиц в кластере несколько, центром считается частица с наибольшей координатой y.
В каждой строке текстового файла хранится информация об одной частице: координаты x и y, проекции вектора скорости Vx и Vy, масса m и признак.
Значения даны в одинаковых для всех частиц единицах измерения, обозначения единиц измерения в файле не приводятся.
Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты, вектор скорости, масса, а также признак, характеризующий внутреннее строение частицы, обозначаемый числами от I до VII (в римской системе счисления).
Учёный решил провести кластеризацию частиц по значениям модуля их момента импульса относительно начала координат, то есть разбить их множество на K непересекающихся непустых подмножеств (кластеров), таких, что модуль разности моментов импульса любых двух частиц каждого подмножества не превосходит значения R. Гарантируется, что такое разбиение существует и единственно для заданного R.
Будем называть центром кластера такую его частицу, для которой сумма Манхэттенских расстояний до всех остальных частиц этого же кластера минимальна.
Если таких частиц в кластере несколько, центром считается частица с наибольшей координатой y.
В каждой строке текстового файла хранится информация об одной частице: координаты x и y, проекции вектора скорости Vx и Vy, масса m и признак.
Значения даны в одинаковых для всех частиц единицах измерения, обозначения единиц измерения в файле не приводятся.
Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции.
Количество строк в файле не превышает 10 000.
Абсолютная величина каждого числового значения не превышает 100,0.
Известно, что все описанные в файле частицы подразделяются ровно на пять кластеров (K=5) с R=2,5 для каждого.
Для каждого кластера определите его центр, затем найдите два числа: Q1 — сумму модулей скоростей √(Vx²+Vy²) всех найденных центров кластеров и Q2 — наименьшее евклидово расстояние между двумя разными частицами одного кластера, имеющими признак III или V, при условии, что угол между их векторами скоростей превышает 90 градусов (скалярное произведение строго отрицательно: Vx1 · Vx2 + Vy1 · Vy2 < 0).
В ответе: целая часть Q1 × 10 000, затем целая часть Q2 × 10 000.
Для справки
Модуль момента импульса частицы массы m, находящейся в точке с координатами x и y и обладающей скоростью V⃗=(Vx;Vy), вычисляется по формуле:
L = m · |x · Vy - y · Vx|
Манхэттенское расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле:
dM(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.
Типовой пример имеет иллюстративный характер.
Для выполнения задания используйте данные из прилагаемого файла