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