Решение: Кластеризация звёздных точек
Задание выполняется с использованием прилагаемых файлов.
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $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}$.
Каждая звезда характеризуется спектральным классом и классом светимости. Спектральные классы $O$, $B$, $A$, $F$, $G$, $K$, $M$ соответствуют голубому, бело-голубому, белому, жёлто-белому, жёлтому, оранжевому и красному цветам. Каждый спектральный класс делится на подклассы от 0 до 9 в порядке уменьшения температуры. Обозначение подкласса ставится после обозначения спектрального класса, например $B2$.
Классы светимости обозначаются римскими цифрами от $I$ до $VII$: $I$ — сверхгигант, $II$ — яркий гигант, $III$ — гигант, $IV$ — субгигант, $V$ — карлик, $VI$ — субкарлик, $VII$ — белый карлик.
В файле A хранится информация о точках двух кластеров, где $H=6{,}0$ и $W=5{,}5$ для каждого кластера. В каждой строке сначала записаны координаты $x$ и $y$ одной звезды, затем для звёзд классов светимости $I$–$VI$ указаны спектральный класс, подкласс и класс светимости. Обозначения классов не разделяются. Для звёзд класса светимости $VII$ спектральный класс и подкласс не указываются. Количество точек не превышает 2000.
В файле Б хранятся координаты точек трёх кластеров при тех же значениях $H=6{,}0$ и $W=5{,}5$. Количество точек не превышает 10 000. Структура хранения информации аналогична структуре файла А.
Для файла А определите координаты центра каждого кластера, затем найдите $A_1$ — количество бело-голубых ярких гигантов, расположенных на расстоянии не более 1,5 от центра кластера, содержащего наименьшее количество точек, и $A_2$ — расстояние между центрами кластеров.
Для файла Б определите координаты центра каждого кластера, затем найдите $B_1$ — наибольшее расстояние от центра кластера до жёлтого карлика, принадлежащего этому кластеру, и $B_2$ — наибольшее количество оранжевых карликов в одном кластере.
В ответе запишите четыре числа: в первой строке сначала $A_1$, затем целую часть произведения $A_2\cdot 10000$; во второй строке сначала целую часть произведения $B_1\cdot 10000$, затем $B_2$.
Пример организации данных в одном из исходных файлов для случая четырёх звёзд:
$5{,}01788\ 8{,}32466\ G2V$
$4{,}289251\ 6{,}955186\ VII$
$4{,}619358\ 5{,}524697\ B7V$
$6{,}91934\ 20{,}425391\ G2V$
Пример приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Решение по шагам
8 шаговПрочитать файлы и сохранить для каждой звезды координаты, спектральный класс, подкласс и класс светимости. Для белых карликов спектральные данные отсутствуют.
Разбить точки на кластеры. Так как размеры ограничивающих прямоугольников равны $H=6{,}0$ и $W=5{,}5$, точки одного кластера должны помещаться в одном таком прямоугольнике, а прямоугольники разных кластеров не должны пересекаться.
Для каждого найденного кластера перебрать все его точки и вычислить сумму расстояний от каждой точки до остальных по формуле $d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$. Точка с минимальной суммой является центром кластера.
Для файла A выбрать кластер с наименьшим числом точек. В нём посчитать бело-голубые яркие гиганты, то есть звёзды класса $B$ с любым подклассом и классом светимости $II$, на расстоянии не более $1{,}5$ от центра. Это значение равно $A_1$.
Для файла A вычислить расстояние между двумя центрами и взять целую часть произведения $A_2\cdot 10000$.
Для файла Б в каждом кластере найти жёлтые карлики, то есть звёзды класса $G$ с классом светимости $V$, и вычислить расстояние от каждой такой звезды до центра её кластера. Максимальное расстояние равно $B_1$.
Для файла Б в каждом кластере посчитать оранжевых карликов, то есть звёзды класса $K$ с классом светимости $V$. Максимальное из полученных количеств равно $B_2$.
Записать четыре полученных целых числа в требуемом порядке.
Точный ответ невозможно вычислить без содержимого файлов A и Б.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Используют среднее арифметическое координат вместо точки кластера с минимальной суммой расстояний.
Путают спектральный класс $B$ с классом светимости $II$.
Считают бело-голубыми звёзды класса $A$, хотя бело-голубой цвет соответствует классу $B$.
Для жёлтых звёзд используют класс $K$ вместо класса $G$.
Забывают умножить расстояния на 10000 перед взятием целой части.
Включают белых карликов в подсчёт звёзд с заданным спектральным классом.