Пример решения: кластеризация звёзд

Решение №29357

27A

from math import dist

# Открываем файл с данными
f = open('files/27_A_29357.txt')


# Функция для поиска центра кластера
# Центр — это такая точка кластера,
# у которой сумма расстояний до остальных точек минимальна
def centroid(cl):

    res = []  # сюда будем сохранять [сумма_расстояний, точка]

    # Перебираем каждую точку кластера
    for p1 in cl:

        s = 0  # сумма расстояний от текущей точки до остальных

        # Считаем расстояния до всех точек кластера
        for p2 in cl:
            s += dist(p1[:2], p2[:2])

        # Сохраняем результат
        res.append([s, p1])

    # Берём точку с минимальной суммой расстояний
    return min(res)[1]


data = []

# Читаем все точки из файла
for line in f:

    # Заменяем запятые на точки
    # и разбиваем строку на x, y и информацию о звезде
    x, y, info = line.replace(',', '.').split()

    # Сохраняем:
    # x, y — координаты
    # info — спектральный класс и класс светимости
    data.append([float(x), float(y), info])

# Копия всех данных
# понадобится позже для поиска красных гигантов
data_original = data[:]

clusters = []

# Пока есть необработанные точки
while data:

    # Создаём новый кластер
    # и кладём в него одну точку
    clusters.append([data.pop()])

    # Перебираем точки текущего кластера
    # список будет увеличиваться прямо во время обхода
    for p1 in clusters[-1]:

        # Перебираем все ещё не использованные точки
        for p2 in data[:]:

            # Если точка находится близко,
            # считаем её принадлежащей тому же кластеру
            if dist(p1[:2], p2[:2]) < 1:

                # Добавляем точку в кластер
                clusters[-1].append(p2)

                # Удаляем из общего списка,
                # чтобы не обработать повторно
                data.remove(p2)

# Сортируем кластеры по количееству точек
clusters.sort(key=len)

# Берём центр кластера с минимальным количеством точек
center = centroid(clusters[0])

# Ищем все красные гиганты:
# M — красный спектральный класс
# III — гигант
wk = [x for x in data_original
      if x[2][0] == 'M' and x[2][2:] == 'III']

res = []

# Для каждого красного гиганта считаем расстояние до центра
for p1 in wk:

    res.append([dist(p1[:2], center[:2]), p1[:2]])

# Сортируем по расстоянию
res.sort()

# Берём ближайшего красного гиганта
Ax, Ay = res[0][1]

# Выводим ответ по условию задачи
print(int(Ax * 10_000), int(Ay * 10_000))

27B

from math import dist

# Открываем файл с данными
f = open('files/27_B_29357.txt')


# Функция поиска центра кластера
# Центр — точка, у которой сумма расстояний
# до всех остальных точек кластера минимальна
def centroid(cl):

    res = []  # сюда будем сохранять [сумма_расстояний, точка]

    # Перебираем все точки кластера
    for p1 in cl:

        s = 0  # сумма расстояний от текущей точки

        # Считаем расстояния до всех остальных точек
        for p2 in cl:
            s += dist(p1[:2], p2[:2])

        # Сохраняем результат
        res.append([s, p1])

    # Возвращаем точку с минимальной суммой расстояний
    return min(res)[1]


data = []

# Считываем данные из файла
for line in f:

    # Заменяем запятые на точки
    # и разделяем строку на части
    x, y, info = line.replace(',', '.').split()

    # Сохраняем:
    # x, y — координаты
    # info — информация о звезде
    data.append([float(x), float(y), info])

# Копия исходных данных
data_original = data[:]

clusters = []

# Пока есть необработанные точки
while data:

    # Создаём новый кластер
    # и кладём в него одну точку
    clusters.append([data.pop()])

    # Перебираем точки текущего кластера
    # список может увеличиваться прямо во время обхода
    for p1 in clusters[-1]:

        # Перебираем ещё не использованные точки
        for p2 in data[:]:

            # Если точки расположены близко,
            # считаем их принадлежащими одному кластеру
            if dist(p1[:2], p2[:2]) < 1:

                # Добавляем точку в кластер
                clusters[-1].append(p2)

                # Удаляем из общего списка
                data.remove(p2)

# print(len(clusters))
# Проверка количества найденных кластеров


og = []

# Для каждого кластера считаем количество
# оранжевых гигантов:
# K — оранжевый спектральный класс
# III — гигант
for cl in clusters:

    og.append(
        len([x for x in cl
             if x[2][0] == 'K' and x[2][2:] == 'III'])
    )

# print(og)
# Проверка количества оранжевых гигантов


# Находим центры всех кластеров
centers = [centroid(cl) for cl in clusters]

# Расстояние между центрами кластеров
# с минимальным и максимальным количеством
# оранжевых гигантов
# (в данном случае это 1-й и 3-й кластеры)
B1 = dist(centers[0][:2], centers[2][:2])

print(int(B1 * 10_000))


# Выбираем жёлтые карлики:
# G — жёлтый спектральный класс
# V — карлик

yk1 = [x for x in clusters[0]
       if x[2][0] == 'G' and x[2][2:] == 'V']

yk2 = [x for x in clusters[1]
       if x[2][0] == 'G' and x[2][2:] == 'V']

yk3 = [x for x in clusters[2]
       if x[2][0] == 'G' and x[2][2:] == 'V']


res = []

# Для каждого кластера
for cl in [yk1, yk2, yk3]:

    # Перебираем все пары жёлтых карликов
    for p1 in cl:
        for p2 in cl:

            # Сохраняем расстояние между ними
            res.append(dist(p1[:2], p2[:2]))

# Находим максимальное расстояние
B2 = max(res)

print(int(B2 * 10_000))