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

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

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

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

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

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

Для А выбираем максимальную абсциссу и отдельно максимальную ординату из найденных центров. Эти координаты не обязаны принадлежать одному центру. После умножения на 10000 и требуемого усечения получаем 49959 и 182737.

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

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

Программа 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': [[1.2265625, 5.7265625, 2.552734375, 8.552734375], [2.6865234375, 7.1865234375, 15.2314453125, 21.2314453125]], 'B': [[15.96484375, 20.96484375, 17.990234375, 23.990234375], [10.548828125, 15.548828125, 17.576171875, 23.576171875], [9.0595703125, 14.0595703125, 6.0693359375, 12.0693359375]]}
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 = [max(c[k] for c in centers_a) 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 также дали одинаковый результат.

Ответ: 49959 182737 69827 122392.