27_0119

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

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

Для каждой звезды дана характеристика: тип цвета, тип светимости (арабская цифра) и её размер, в соответствии с таблицей.

Значения записаны в характеристике слитно: обозначение цвета, светимость (цифра $1$–$7$) и обозначение размера. В данных встречается один экземпляр на файл с цифрой светимости $9$ — это выброс измерения (вне нормального диапазона $1$–$7$), к нижеописанным категориям он не относится ни при каком значении цвета и размера.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Расстояние между двумя точками на плоскости $A(x_1,y_1)$ и $B(x_2,y_2)$:

$$d(A,B)=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}.$$

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

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

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

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

В ответе запишите четыре числа: в первой строке — сначала целую часть произведения $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_0119A.txt
• 27_0119B.txt