Ответ: Кластеризация звёздных точек

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Необходимо разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера лежали внутри прямоугольника со сторонами длиной $H=6{,}0$ и $W=5{,}5$, причём прямоугольники не пересекались. Стороны прямоугольников не обязательно параллельны координатным осям. Такое разбиение существует и единственно.

Центром кластера называется точка этого кластера, сумма расстояний от которой до всех остальных точек минимальна. Расстояние между точками $A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле $d(A,B)=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$.

Каждая звезда характеризуется спектральным классом и классом светимости. Спектральные классы $O$, $B$, $A$, $F$, $G$, $K$, $M$ соответствуют цветам: голубой, бело-голубой, белый, жёлто-белый, жёлтый, оранжевый, красный. Каждый спектральный класс имеет подклассы от 0 до 9. Класс светимости обозначается римскими цифрами от $I$ до $VII$: сверхгигант, яркий гигант, гигант, субгигант, карлик, субкарлик, белый карлик.

В файле A содержится информация о точках двух кластеров, а в файле Б — о точках трёх кластеров. В каждой строке записаны координаты звезды и её спектральный класс, подкласс и класс светимости. Для белых карликов класса $VII$ спектральный класс и подкласс не указываются. Количество точек в файле A не превышает 2000, а в файле Б — 10 000.

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

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

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