Решение: Кластеризация звёздных точек
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $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 в порядке уменьшения температуры. Класс светимости обозначается римскими цифрами от 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_x$ и ординату $A_y$ оранжевого субкарлика, ближайшего к центру кластера, который содержит наибольшее количество точек.
Для файла Б определите расстояние $B_1$ между центрами кластеров с наименьшим и наибольшим количеством жёлто-белых ярких гигантов и найдите $B_2$ — наибольшее расстояние между белыми яркими гигантами одного кластера.
В ответе запишите четыре числа: в первой строке — целую часть абсолютной величины произведения $A_x\times10000$, затем целую часть абсолютной величины произведения $A_y\times10000$; во второй строке — целую часть произведения $B_1\times10000$, затем целую часть произведения $B_2\times10000$. Для решения используйте данные из прилагаемых файлов.
Решение по шагам
6 шаговПрочитать строки файлов и выделить координаты звёзд, а также их спектральные классы и классы светимости.
Разбить точки на кластеры, используя условие о прямоугольниках со сторонами $H=6{,}0$ и $W=5{,}5$.
Для каждого кластера найти точку, минимизирующую сумму расстояний до всех остальных точек этого кластера.
В файле A выбрать кластер с наибольшим числом точек, среди его оранжевых субкарликов найти ближайшего к центру и вычислить $A_x$ и $A_y$.
В файле Б подсчитать в каждом кластере число жёлто-белых ярких гигантов, определить кластеры с минимумом и максимумом таких звёзд и найти расстояние между их центрами.
Среди белых ярких гигантов каждого кластера найти максимальное попарное расстояние.
Числовой ответ зависит от содержимого файлов A и Б.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Использование координат геометрического центра вместо точки-звезды, минимизирующей сумму расстояний.
Путаница между спектральным классом и классом светимости.
Неверное толкование обозначения белого яркого гиганта: спектральный класс A и класс светимости II.
Округление вместо взятия целой части после умножения на 10000.
Поиск максимального расстояния между звёздами разных кластеров при вычислении $B_2$.