Задание 27

Решение 1. Пороговая кластеризация со звёздными типами

Шаг 1. Подключаем инструменты

from math import hypot
import re

hypot считает расстояние на плоскости, re разберёт характеристику вида Y7III.

Шаг 2. Читаем звёзды из файла

def read_stars(path):
    stars = []
    for line in open(path, encoding="utf-8"):
        line = line.strip().replace("\t", " ")
        if not line:
            continue
        parts = line.replace(",", ".").split()
        x, y = float(parts[0]), float(parts[1])
        char = parts[2]
        stars.append((x, y, char))
    return stars

В каждой строке — x, y и характеристика.

Запятую в координатах меняем на точку.

Шаг 3. Центр кластера — медоид

def center(cluster):
    best = cluster[0]
    best_sum = 10 ** 18
    for p in cluster:
        s = sum(hypot(p[0] - q[0], p[1] - q[1]) for q in cluster)
        if s < best_sum:
            best_sum = s
            best = p
    return best

Центр — звезда кластера с минимальной суммой расстояний до всех остальных звёзд кластера.

Шаг 4. Разбираем характеристику

def parse_char(char):
    m = re.fullmatch(r"([A-Z]+)(\d+)([IVX]+)", char)
    return m.groups() if m else (None, None, None)

Из строки вроде Y7III получаем: цвет Y, светимость 7, размер III.

Шаг 5. Красный гигант

def is_red_giant(char):
    color, _lum, size = parse_char(char)
    return color == "Y" and size == "III"

По таблице: красный — Y, гигант — размер III.

Шаг 6. Жёлтый карлик

def is_yellow_dwarf(char):
    color, _lum, size = parse_char(char)
    return color == "Z" and size == "V"

Жёлтый — Z, карлик — размер V.

Шаг 7. Файл A: два кластера

stars_a = read_stars("27-1-A.txt")
clusters_a = [
    [p for p in stars_a if p[1] < 9],
    [p for p in stars_a if p[1] >= 9],
]

По графику точки файла A делятся горизонтальной границей около y = 9.

Имя файла в песочнице: 27-1-A.txt.

Шаг 8. Наименьший кластер и его центр

small = min(clusters_a, key=len)
c_small = center(small)

Нужен кластер с меньшим числом точек — и его медоид.

Шаг 9. Все красные гиганты файла A

reds = [p for p in stars_a if is_red_giant(p[2])]

Собираем красные гиганты по всему файлу A — не только из малого кластера.

Шаг 10. A1 и A2

dists = [hypot(c_small[0] - r[0], c_small[1] - r[1]) for r in reds]
A1, A2 = min(dists), max(dists)
print(int(A1 * 10000), int(A2 * 10000))

A1 — минимальное, A2 — максимальное расстояние от центра малого кластера до красных гигантов.

Умножаем на 10 000 и берём целую часть.

Шаг 11. Файл B: три кластера

stars_b = read_stars("27-1-B.txt")
clusters_b = [
    [p for p in stars_b if p[0] > 20],
    [p for p in stars_b if p[0] <= 20 and p[1] > 22],
    [p for p in stars_b if p[0] <= 20 and p[1] <= 22],
]

Один кластер справа (x > 20), два слева — выше и ниже y = 22.

Шаг 12. Центры трёх кластеров B

centers = [center(c) for c in clusters_b]

Для каждого кластера B считаем медоид.

Шаг 13. B1 — ближайшая пара жёлтых карликов

yd_counts = []
pair_mins = []
for cl in clusters_b:
    yds = [p for p in cl if is_yellow_dwarf(p[2])]
    yd_counts.append(len(yds))
    if len(yds) >= 2:
        m = min(
            hypot(yds[i][0] - yds[j][0], yds[i][1] - yds[j][1])
            for i in range(len(yds))
            for j in range(i + 1, len(yds))
        )
        pair_mins.append(m)
B1 = min(pair_mins)

В каждом кластере считаем жёлтых карликов и минимальное расстояние между двумя разными. B1 — наименьшее из этих минимумов.

Шаг 14. B2 и вывод ответа

i_min = min(range(3), key=lambda i: yd_counts[i])
i_max = max(range(3), key=lambda i: yd_counts[i])
B2 = hypot(
    centers[i_min][0] - centers[i_max][0],
    centers[i_min][1] - centers[i_max][1],
)
print(int(B1 * 10000), int(B2 * 10000))

B2 — расстояние между центрами кластеров с минимальным и максимальным числом жёлтых карликов.

Ожидаемый ответ: 4940 74302 / 2199 189261.