27_0111

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

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

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Расстояние между точками $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$ до $9$ в порядке уменьшения температуры. Обозначение подкласса ставится после обозначения спектрального класса (например, B2). Класс светимости звезды обозначим римскими цифрами от I до VII.

Для звёзд классов светимости I–VI в файле указываются спектральный класс, подкласс и класс светимости слитно (например, B7II). Для звёзд класса светимости VII (белый карлик) спектральный класс и подкласс не указываются, пишется только «VII».

В файле А хранятся данные о звёздах двух кластеров, где $H=6{,}5$, $W=5{,}0$. Известно, что количество звёзд не превышает $1500$.

В файле Б хранятся данные о звёздах трёх кластеров, где $H=6{,}5$, $W=5{,}5$. Известно, что количество звёзд не превышает $9000$. Структура хранения аналогична файлу А.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: $A_1$ — наибольшее расстояние между двумя разными бело-голубыми яркими гигантами одного кластера, и $A_2$ — среднее арифметическое расстояний от центра кластера с наименьшим количеством точек до всех голубых сверхгигантов этого кластера.

Для файла Б определите координаты центра каждого кластера, затем найдите два числа: $B_1$ — расстояние между центрами кластеров с наименьшим и наибольшим количеством красных карликов, и $B_2$ — сумма расстояний от антицентра кластера с наибольшим количеством точек до жёлто-белых субгигантов этого кластера (антицентр — точка кластера с максимальной суммой расстояний до остальных его точек).

В ответе запишите четыре числа: в первой строке — сначала целую часть произведения $A_1\cdot 10\thinspace 000$, затем целую часть произведения $A_2\cdot 10\thinspace 000$; во второй строке — сначала целую часть абсолютного значения произведения $B_1\cdot 10\thinspace 000$, затем целую часть абсолютного значения произведения $B_2\cdot 10\thinspace 000$.

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

Файлы к заданию:

• 27_0111A.txt
• 27_0111B.txt