Задание 27: кластеризация данных

Разбор: как решать задание 27

Авторское

Задание выполняется с использованием прилагаемого файла.

Астроном составляет карту звёздного неба. Звёзды на карте образуют кластеры — компактные группы; каждая звезда принадлежит ровно одному кластеру, а кластеры расположены далеко друг от друга — гораздо дальше, чем соседние звёзды одного кластера. Центр кластера — это одна из звёзд кластера, сумма расстояний от которой до всех остальных звёзд этого кластера минимальна. Для каждого кластера центр единственен.

В каждой строке файла записана информация об одной звезде: сначала координата x, затем координата y, далее — обозначение звезды. Для звёзд классов светимости I–VI обозначение состоит из спектрального класса (буква, задающая цвет звезды), подкласса (цифра от 0 до 9) и класса светимости (римское число); части обозначения ничем не разделяются, например N9I — оранжевый сверхгигант подкласса 9. Для звёзд класса светимости VII спектральный класс и подкласс не указываются: обозначение — просто VII. Значения в строке разделены символом табуляции, дробная часть чисел отделяется запятой.

Обозначения цветов и классов светимости:

В файле А записаны данные о звёздах двух кластеров.

В файле ровно одна звезда — оранжевый сверхгигант подкласса 9. Найдите A₁ — наименьшее, и A₂ — наибольшее из расстояний от этой звезды до центров кластеров.

В ответе запишите два числа: сначала целую часть произведения A₁ × 10 000, затем целую часть произведения A₂ × 10 000.

Для справки

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂) на плоскости вычисляется по формуле

d(A, B) = √((x₂ − x₁)² + (y₂ − y₁)²).

Запишите два числа через пробел.

Файлы к заданию: Звёздное небо A (задание 27).txt