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

Решение.
Используем координаты из двух файлов, а не пример рисунка в условии. В текстовых файлах первая строка — заголовок X Y, далее по одной точке на строку; десятичный разделитель — запятая. Точка нумеруется по строкам данных, начиная с 1, без заголовка.

Сначала выделим кластеры. Для этих конкретных файлов подходят следующие прямоугольники с границами x₁ < x < x₂ и y₁ < y < y₂. Стороны параллельны осям; условие допускает и такой частный случай. Размеры каждого прямоугольника А равны 4,5 × 6, каждого прямоугольника Б — 5 × 6.

Внутри каждого файла прямоугольники попарно не пересекаются. Все точки А входят ровно в один из двух прямоугольников. В Б за пределами трёх прямоугольников остаются ровно три точки: 114, 266, 506 по номерам строк данных. Каждая из них удалена от любой другой точки больше диагонали прямоугольника √61; она не может входить вместе с другой точкой в такой кластер. Остальные точки все сохранены. По гарантированной в условии единственности разбиения найденные группы и есть требуемые кластеры.

Центр здесь — одна из исходных точек кластера, а не среднее арифметическое координат. Для каждого кандидата p считаем D(p) = Σ d(p, q), где q пробегает все точки того же кластера. Собственное расстояние равно нулю. Сравниваем D для всех кандидатов и выбираем точку с наименьшей суммой. Сумма квадратов расстояний дала бы другой критерий и не используется.

Полученные центры:

Для А складываем две абсциссы и делим на 2; отдельно поступаем с ординатами. После умножения каждого среднего на 10000 берём абсолютную величину целой части: 55295 и 136872.

В Б наименьший кластер — № 3, в нём 72 точек; наибольший — № 1, в нём 397. Сравниваем количества точек, а не координаты или суммы расстояний.

Для Qₓ и Qᵧ берём суммы соответствующих координат двух выбранных центров. После умножения на 10000, взятия целой части и абсолютного значения получаем 319184 и 448643. Промежуточные координаты не округляем.

Программа Python. Сохраняем исходные текстовые файлы А и Б под именами A.txt и B.txt. Прямоугольники ниже рассчитаны по этим данным; для другого набора координат их требуется определить заново.

from math import dist, fsum, hypot, isqrt
from fractions import Fraction


def load(name):
    with open(name, encoding="utf-8-sig") as f:
        assert f.readline().split() == ["X", "Y"]
        return [tuple(map(Fraction, line.replace(",", ".").split()))
                for line in f if line.strip()]


def analyze(points, rectangles, anomalies):
    groups = [[] for box in rectangles]
    omitted = []
    for index, point in enumerate(points):
        x, y = point
        hits = [i for i, (x1, x2, y1, y2) in enumerate(rectangles)
                if x1 < x < x2 and y1 < y < y2]
        assert len(hits) <= 1
        if hits:
            groups[hits[0]].append(index)
        else:
            omitted.append(index)
    assert len(omitted) == anomalies
    for i in omitted:
        assert min(dist(points[i], p) for j, p in enumerate(points)
                   if j != i) > hypot(6, 5)
    centers = []
    for group in groups:
        assert group
        best = min(group, key=lambda i:
                   fsum(dist(points[i], points[j]) for j in group))
        centers.append(points[best])
    return groups, centers


def square(a, b):
    return sum((x - y) ** 2 for x, y in zip(a, b))


def scaled_root(q):
    q *= 100000000
    return isqrt(divmod(q.numerator, q.denominator)[0])

boxes = {'A': [[4.8095703125, 9.3095703125, 17.078125, 23.078125], [1.6484375, 6.1484375, 4.1611328125, 10.1611328125]], 'B': [[4.01953125, 9.01953125, 18.8974609375, 24.8974609375], [15.6982421875, 20.6982421875, 23.3056640625, 29.3056640625], [23.15625, 28.15625, 19.8916015625, 25.8916015625]]}
A = load("A.txt")
B = load("B.txt")
groups_a, centers_a = analyze(A, boxes["A"], 0)
groups_b, centers_b = analyze(B, boxes["B"], 3)
pa = [sum(c[k] for c in centers_a) * Fraction(1, 2)
      for k in (0, 1)]
print(*(abs(int(v * 10000)) for v in pa))
order = sorted(range(3), key=lambda i: len(groups_b[i]))
a, b = centers_b[order[0]], centers_b[order[-1]]
qb = [a[k] + b[k] for k in (0, 1)]
print(*(abs(int(v * 10000)) for v in qb))

Проверка. Каждый кандидат в каждом кластере проверен суммой евклидовых расстояний. Два лучших кандидата дополнительно сопоставлены с точностью 60 десятичных знаков; минимум единственен. Независимое выделение групп по близким точкам дало те же группы, центры и три аномалии. Варианты TXT и XLSX также дали одинаковый результат.

Ответ: 55295 136872 319184 448643.