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

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

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

После нахождения центров усредняем именно их координаты. Каждый кластер в этом среднем имеет одинаковый вес независимо от количества точек в нём:
Pₓ = x₁ + … + xₖk, Pᵧ = y₁ + … + yₖk.
Для файла A: Pₓ = 2.621655502000, Pᵧ = 2.418253979500. После умножения на 10000, взятия целой части и модуля получаем 26216 24182.
Для файла B: Pₓ = 15.089196643000, Pᵧ = 6.375451118000. После умножения на 10000, взятия целой части и модуля получаем 150891 63754.
Программа на 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 = [[0.5, 6.5, -5.5, 0.5], [-2.2, 3.8, 4.8, 10.8]]

boxes_B = [[12, 20, 9.5, 17.5], [21.5, 29.5, -4.5, 3.5], [0, 8, 3, 11]]

for letter, boxes in [('A', boxes_A), ('B', boxes_B)]:
    groups = split_points(read_points('1_27_' + letter + '.txt'), boxes)
    centers = [center(group) for group in groups]
    px = mean(p[0] for p in centers)
    py = mean(p[1] for p in centers)
    print(abs(int(px * 10000)), abs(int(py * 10000)))

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