Задание EGEINFEAFDD5: Эффективная обработка данных и кластеры

Решение.
Распакуем скачанный архив и сохраним два текстовых файла 1_27_A.txt и 1_27_B.txt рядом с программой. Архив на странице содержит эти два неизменённых файла из официального комплекта ФИПИ 2026 года. Для вычислений нужны реальные точки из файлов: иллюстративный рисунок или пример строк из условия их не заменяет.
Считываем координаты, заменяя десятичную запятую точкой. Строку заголовка X Y, если она есть, пропускаем. В файле A получаем 235 точек, в файле B — 1851. Нумерация точек ниже начинается с 1 и не включает заголовок.
Сначала определим кластеры. По диаграмме фактических данных выбираем следующие прямоугольники; затем программа проверяет принадлежность каждой точки ровно одному из них:

Все прямоугольники имеют ширину 5,5 и высоту 6, как требуется в условии. Внутри каждого файла прямоугольники попарно не пересекаются, все кластеры непусты и каждая исходная точка попала ровно в один из них. Следовательно, найдено допустимое разбиение. По гарантии единственности в условии это и есть искомые кластеры. Выбранные границы относятся именно к данным этого файла.
Центр ищем среди всех точек соответствующего кластера. Для каждой точки p вычисляем S(p) = Σ d(p, q), где q пробегает все точки этого же кластера, и выбираем точку с минимальным S. Саму p можно включить в сумму: её расстояние до себя равно нулю.
Используем евклидово расстояние d(p, q) = √(xₚ − x_q)² + (yₚ − y_q)². Сумма квадратов расстояний и среднее арифметическое координат всех точек задают другие критерии и здесь не подходят. Полный перебор проверяет каждого кандидата; сравнение со вторым результатом подтверждает строгий минимум.
Полученные центры:

Для файла A выбираем кластер A1: он содержит 114 точек, а второй — 121. Ищем ближайшего к его центру красного гиганта. У такого объекта первая буква кода M, затем идёт одна цифра, а весь оставшийся суффикс равен III. Проверка только наличия буквы M или символа I дала бы неверную группу.
Перебор красных гигантов всего файла даёт точку № 144 с координатами (4.469472; 6.975433) и классом M0III. Она принадлежит выбранному кластеру. Координаты этой звезды, а не координаты центра, нужно умножить на 10000 и взять целые части модулей: 44694 69754.
Для файла B отдельно считаем оранжевых гигантов: первая буква K, весь суффикс после цифры — III. Жёлтые карлики имеют первую букву G и суффикс строго V. Суффиксы IV, VI и отдельная запись VII под это условие не подходят.

Для B₁ берём центры кластеров B3 и B1. Их расстояние равно 13.871632304990; целая часть произведения на 10000 равна 138716.
Для B₂ перебираем все неупорядоченные пары жёлтых карликов внутри каждого кластера и выбираем общий максимум. Пары из разных кластеров не рассматриваем. Максимум достигается в B1 на точках № 175 (12.237969; 23.556475; G2V) и № 1626 (12.580719; 26.942122; G5V). Расстояние равно 3.402952125891, поэтому второе число равно 34029.
Программа на Python 3:

from math import dist, fsum
from statistics import mean

def read_points(filename):
    rows = []
    with open(filename, encoding='utf-8-sig') as source:
        for line in source:
            parts = line.replace(',', '.').split()
            if not parts or parts[0].upper() == 'X':
                continue
            x, y = map(float, parts[:2])
            rows.append((x, y, parts[2] if len(parts) > 2 else ''))
    return rows

def split_points(rows, boxes):
    groups = [[] for _ in boxes]
    for point in rows:
        x, y = point[:2]
        matches = [i for i, (x1, x2, y1, y2) in enumerate(boxes)
                   if x1 <= x <= x2 and y1 <= y <= y2]
        assert len(matches) == 1
        groups[matches[0]].append(point)
    assert all(groups)
    return groups

def center(group):
    return min(group, key=lambda p: fsum(dist(p[:2], q[:2])
                                       for q in group))

boxes_A = [[2.5, 8, 5, 11], [5, 10.5, 17, 23]]

boxes_B = [[9, 14.5, 22, 28], [10, 15.5, 33.5, 39.5], [16, 21.5, 34, 40]]

def star_type(point, color, luminosity):
    code = point[2]
    return (len(code) >= 3 and code[0] == color
            and code[1].isdigit() and code[2:] == luminosity)

stars_a = read_points('1_27_A.txt')
groups_a = split_points(stars_a, boxes_A)
centers_a = [center(group) for group in groups_a]
smallest = min(range(len(groups_a)), key=lambda i: len(groups_a[i]))
red = [p for p in stars_a if star_type(p, 'M', 'III')]
nearest = min(red, key=lambda p: dist(p[:2], centers_a[smallest][:2]))
print(int(abs(nearest[0] * 10000)), int(abs(nearest[1] * 10000)))

stars_b = read_points('1_27_B.txt')
groups_b = split_points(stars_b, boxes_B)
centers_b = [center(group) for group in groups_b]
orange_counts = [sum(star_type(p, 'K', 'III') for p in group)
                 for group in groups_b]
lo = min(range(len(groups_b)), key=lambda i: orange_counts[i])
hi = max(range(len(groups_b)), key=lambda i: orange_counts[i])
b1 = dist(centers_b[lo][:2], centers_b[hi][:2])
b2 = 0
for group in groups_b:
    yellow = [p for p in group if star_type(p, 'G', 'V')]
    for i in range(len(yellow)):
        for j in range(i + 1, len(yellow)):
            b2 = max(b2, dist(yellow[i][:2], yellow[j][:2]))
print(int(b1 * 10000), int(b2 * 10000))

Результат выполнения:
44694 69754
138716 34029
Проверка полноты: каждая входная точка проверена при разбиении, в каждом кластере просмотрены все кандидаты в центры и все расстояния до остальных точек. Независимый расчёт другим алгоритмом разбиения подтвердил все составы кластеров и номера центров. Финальные целые числа также проверены вычислениями с исходными десятичными координатами без потери точности при округлении.
Основные затраты времени — O(N²) для полного перебора расстояний; память — O(N). Матрица всех попарных расстояний не хранится.
Ответ: 44694 69754 138716 34029.