Задание 27

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат.

Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются.

Стороны прямоугольников не обязательно параллельны координатным осям.

Гарантируется, что такое разбиение существует и единственно.

Для каждой звезды дана характеристика: тип цвета, тип светимости и её размер в соответствии с таблицей.

Обозначение	Цвет	Обозначение	Размер
G	белый	I	сверхгигант
J	зелёный	II	яркий гигант
L	синий	III	гигант
N	оранжевый	IV	субгигант
Y	красный	V	карлик
S	голубой	VI	субкарлик
Z	жёлтый	VII	квазар

В файле A хранятся данные о звёздах двух кластеров, где H = 6,5, W = 4,5 для каждого кластера.

В каждой строке записана координата x, затем координата y, а затем её характеристика.

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат.

Стороны прямоугольников не обязательно параллельны координатным осям.

Гарантируется, что такое разбиение существует и единственно.

Для каждой звезды дана характеристика: тип цвета, тип светимости и её размер в соответствии с таблицей.

Обозначение	Цвет	Обозначение	Размер
G	белый	I	сверхгигант
J	зелёный	II	яркий гигант
L	синий	III	гигант
N	оранжевый	IV	субгигант
Y	красный	V	карлик
S	голубой	VI	субкарлик
Z	жёлтый	VII	квазар

В файле A хранятся данные о звёздах двух кластеров, где H = 6,5, W = 4,5 для каждого кластера.

В каждой строке записана координата x, затем координата y, а затем её характеристика.

Определите координаты центра каждого кластера для файла A, затем найдите два числа: A_x — абсцисса ближайшего к центроиду жёлтого карлика кластера с наибольшим количеством звёзд, и A_y — ордината ближайшего к центроиду жёлтого карлика кластера с наибольшим количеством звёзд.

В ответе укажите целые части произведений A_x × 10 000 и A_y × 10 000.

Решение 1. Кластеризация звёзд (файл A)

Шаг 1. Считывание координат

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

Из файла читаются точки (x, y), координаты приводятся к float и складываются в список.

Шаг 2. Центры кластеров

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

Для каждого кластера центр ищется как медоид — точка с минимальной суммой расстояний до остальных точек кластера.

Шаг 3. Разбиение файла A

Две группы звёзд: y > x + 3 и остальные.

Шаг 4. Разбиение файла B

Файл B в условии не используется — данные в одном CSV.

Шаг 5. Вычисление ответа

Для A: Берём кластер с наибольшим числом звёзд, находим его центроид.

Для B: Среди жёлтых карликов (Z?

V, G?

V) выбираем ближайший к центроиду.

Шаг 6. Формат вывода

Итоговые значения масштабируются по условию задачи (обычно умножение на 10000 и взятие целой части) и выводятся двумя строками: отдельно для файла A и отдельно для файла B.