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