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

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

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

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

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

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

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

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

Q₁ — евклидово расстояние между этими двумя центрами. Для Q₂ перебираем все точки каждого кластера и расстояния до его собственного центра, после чего берём наибольшее из всех расстояний. Максимум достигается на точке № 575. Целые части произведений на 10000 равны 142058 и 25299. Для усечения квадратного корня используем точный целочисленный корень от масштабированного квадрата расстояния.

Программа 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.7255859375, 9.2255859375, 9.234375, 15.234375], [1.5595703125, 6.0595703125, 3.1298828125, 9.1298828125]], 'B': [[8.9609375, 13.9609375, 11.701171875, 17.701171875], [19.048828125, 24.048828125, 21.8349609375, 27.8349609375], [12.345703125, 17.345703125, 20.603515625, 26.603515625]]}
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 = [min(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]]
q1 = square(a, b)
q2 = max(square(B[j], centers_b[i])
         for i, group in enumerate(groups_b) for j in group)
print(scaled_root(q1), scaled_root(q2))

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

Ответ: 38471 61225 142058 25299.