Кластеризация звёздных точек
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $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$. Для решения используйте данные из прилагаемых файлов.
Условие как в банке ФИПИ — открыть и сверить
| ||||||||||||||||||||||||||||||||||||||
| | ||||||||||||||||||||||||||||||||||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Сначала разделите точки на кластеры: два кластера для файла A и три кластера для файла Б.
2Наводящая — какие числа считатьуровень 2 из 3
Для каждой точки вычислите сумму расстояний до остальных точек её кластера. Точка с минимальной суммой является центром кластера.
3Прямая — фактически решениеуровень 3 из 3
Отфильтруйте звёзды по обозначениям спектрального класса и класса светимости, вычислите требуемые расстояния, умножьте результаты на 10000 и отбросьте дробную часть.