27_0181

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $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}$.

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

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

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

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

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

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

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

• 27_0181A.txt
• 27_0181B.txt