(А.Богданов) Рассматриваются частицы на плоскости.
У каждой частицы есть декартовы координаты, вектор скорости, масса и тип, который обозначается одной латинской буквой от A до F.
Учёный решил провести кластеризацию частиц по модулю их импульса.
Для этого множество частиц разбивается на K непересекающихся непустых подмножеств (кластеров) так, чтобы модуль разности модулей импульсов любых двух частиц одного подмножества не превосходил значения R. Гарантируется, что при заданном R такое разбиение существует и единственно.
Центром кластера будем называть такую его частицу, для которой наибольший из модулей разности импульсов с остальными частицами этого кластера минимален.
Для каждого кластера гарантируется единственность его центра.
В каждой строке текстового файла хранится информация об одной частице: координаты x и y, проекции вектора скорости Vx и Vy, масса m и тип.
Значения даны в одинаковых для всех частиц единицах измерения, поэтому единицы в файле не указываются.
(А.Богданов) Рассматриваются частицы на плоскости.
У каждой частицы есть декартовы координаты, вектор скорости, масса и тип, который обозначается одной латинской буквой от A до F.
Учёный решил провести кластеризацию частиц по модулю их импульса.
Для этого множество частиц разбивается на K непересекающихся непустых подмножеств (кластеров) так, чтобы модуль разности модулей импульсов любых двух частиц одного подмножества не превосходил значения R. Гарантируется, что при заданном R такое разбиение существует и единственно.
Центром кластера будем называть такую его частицу, для которой наибольший из модулей разности импульсов с остальными частицами этого кластера минимален.
Для каждого кластера гарантируется единственность его центра.
В каждой строке текстового файла хранится информация об одной частице: координаты x и y, проекции вектора скорости Vx и Vy, масса m и тип.
Значения даны в одинаковых для всех частиц единицах измерения, поэтому единицы в файле не указываются.
Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции.
В файле не больше 10 000 строк.
Абсолютная величина каждого числового значения не превосходит 100,0.
Известно, что все частицы из файла разбиваются ровно на 3 кластера (K=3) при R=1,5.
Для каждого кластера определите его центр, затем найдите два числа.
Q1 – наибольшее евклидово расстояние между центрами кластеров.
Q2 – наименьшее среди всех кластеров среднее арифметическое модулей импульса частиц типа B. Гарантируется, что в каждом кластере есть хотя бы одна частица типа B.
В ответе запишите два числа: сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.
Для справки
Модуль импульса p частицы массы m, обладающей скоростью V = (Vx; Vy), вычисляется по формуле:
p = m · √(Vx² + Vy²)
Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:
d(A, B) = √((x₂ - x₁)² + (y₂ - y₁)²)
Типовой пример организации данных во входном файле
Три строки файла для трёх частиц:
0,67 –2,14 3,0 –4,0 0,2 C
3,14 7,22 6,0 8,0 0,5 A
–1,33 5,56 0,00 5,22 0,456 F
Для частицы из первой строки модуль импульса равен 1,0.
Для частицы из второй строки он равен 5,0.