Решение: Кластеризация звёздных точек
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Необходимо разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера лежали внутри прямоугольника со сторонами длиной $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$ — наибольшее количество белых ярких гигантов в одном кластере.
Для выполнения задания используйте данные из прилагаемых файлов.
Решение по шагам
7 шаговСчитать координаты и характеристики всех звёзд из файлов A и Б.
Разбить точки каждого файла на кластеры. Для каждой группы необходимо проверить, что все её точки можно разместить внутри прямоугольника со сторонами $6{,}0$ и $5{,}5$, допускающего произвольный поворот, и что прямоугольники разных кластеров не пересекаются.
Для каждого кластера для каждой точки вычислить сумму расстояний до всех остальных точек: $S_i=\sum_{j\ne i}d(P_i,P_j)$. Точка с минимальным значением $S_i$ является центром.
В файле A выбрать кластер с минимальным числом точек. Подсчитать в нём жёлтые субгиганты, то есть звёзды спектрального класса $G$ любого подкласса и класса светимости $IV$, находящиеся на расстоянии не более $1{,}2$ от центра. Это значение равно $A_1$.
Вычислить расстояние между двумя центрами файла A по формуле $A_2=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$ и взять целую часть числа $A_2\cdot10000$.
В файле Б для каждого кластера найти расстояния от его центра до всех оранжевых гигантов, то есть звёзд спектрального класса $K$ любого подкласса и класса светимости $III$. Максимальное расстояние равно $B_1$.
Для каждого кластера подсчитать белых ярких гигантов — звёзд класса светимости $II$. Максимальное из полученных количеств равно $B_2$.
Числа зависят от данных в прилагаемых файлах A и Б; файлы с координатами и характеристиками звёзд не предоставлены.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Путать спектральный класс $G$ жёлтых звёзд с классом светимости.
Путать оранжевые звёзды класса $K$ с жёлтыми звёздами класса $G$.
Считать центром среднее арифметическое координат вместо точки с минимальной суммой расстояний.
Забывать взять целую часть произведений $A_2\cdot10000$ и $B_1\cdot10000$.