Кластеризация звёздных точек
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Необходимо разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера лежали внутри прямоугольника со сторонами длиной $H=6{,}0$ и $W=5{,}5$, причём прямоугольники не пересекались. Стороны прямоугольников не обязательно параллельны координатным осям. Такое разбиение существует и единственно.
Центром кластера называется точка этого кластера, сумма расстояний от которой до всех остальных точек минимальна. Расстояние между точками $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$: сверхгигант, яркий гигант, гигант, субгигант, карлик, субкарлик, белый карлик.
В файле A содержится информация о точках двух кластеров, а в файле Б — о точках трёх кластеров. В каждой строке записаны координаты звезды и её спектральный класс, подкласс и класс светимости. Для белых карликов класса $VII$ спектральный класс и подкласс не указываются. Количество точек в файле A не превышает 2000, а в файле Б — 10 000.
Для файла A определите координаты центров кластеров, затем найдите $A_1$ — количество жёлтых субгигантов, расположенных на расстоянии не более $1{,}2$ от центра кластера с наименьшим количеством точек, и $A_2$ — расстояние между центрами кластеров.
Для файла Б определите координаты центров кластеров, затем найдите $B_1$ — наибольшее расстояние от центра кластера до оранжевого гиганта, принадлежащего этому кластеру, и $B_2$ — наибольшее количество белых ярких гигантов в одном кластере.
Для выполнения задания используйте данные из прилагаемых файлов.
Условие как в банке ФИПИ — открыть и сверить
| ||||||||||||||||||||||||||||||||||||||
| | ||||||||||||||||||||||||||||||||||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Сначала восстановите кластеры по геометрическому условию, перебирая точки и проверяя, могут ли они принадлежать одному прямоугольнику со сторонами $H$ и $W$.
2Наводящая — какие числа считатьуровень 2 из 3
Для каждого найденного кластера вычислите для каждой точки сумму расстояний до всех остальных точек. Точка с минимальной суммой является центром кластера.
3Прямая — фактически решениеуровень 3 из 3
После нахождения центров посчитайте требуемые характеристики звёзд и расстояния. В ответ запишите $A_1$ и целую часть $A_2\cdot10000$ в первой строке, затем целую часть $B_1\cdot10000$ и $B_2$ во второй.