27_0177

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

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

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

В файле Б хранятся данные о звёздах трёх кластеров, где $H=6{,}5$, $W=5{,}5$. Известно, что количество звёзд не превышает 9500. Структура хранения аналогична файлу 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_0177A.txt
• 27_0177B.txt