27_0189

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

Каждая звезда помимо координат характеризуется своим спектральным классом и классом светимости (см. таблицу).

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

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

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

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

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

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

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

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

• 27_0189A.txt
• 27_0189B.txt