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