27_0171

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

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

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

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

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

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

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

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

• 27_0171A.txt
• 27_0171B.txt