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

Решение.

В файле A записано 217 точек, в файле Б — 617. Строка X Y является заголовком. Координаты читаем с десятичной запятой; порядок строк не задаёт принадлежность кластеру. Иллюстративный график условия не используем вместо этих данных.

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

Сначала выделим кластеры. Для этих конкретных файлов подходят следующие прямоугольники с границами, параллельными осям. Запись x₁ < x < x₂, y₁ < y < y₂ задаёт внутренность прямоугольника:

У каждого прямоугольника высота равна 6, ширина для A равна 4,5, для Б равна 5. Указанные прямоугольники попарно не пересекаются: для каждой пары разделены либо интервалы x, либо интервалы y. Проверяем все строки: каждая обычная точка попадает ровно в один прямоугольник; на границах точек нет. В условии гарантирована единственность допустимого разбиения, поэтому найденное разбиение и является искомым. Эти координатные границы относятся именно к приложенным файлам.

В файле A учтены все точки. В файле Б вне трёх прямоугольников остаются ровно три точки:

Каждая из этих трёх точек удалена от любой другой точки больше чем на диагональ прямоугольника √6² + 5² = √61. Они изолированы от основных скоплений. Исключаем именно эти три аномалии; число оставшихся точек равно сумме размеров трёх кластеров в таблице.

Теперь сравниваем S(p) для всех точек каждого кластера. В таблице приведены найденные центры и разность между второй по величине снизу суммой и минимальной суммой. Положительная разность подтверждает единственность найденного минимума:

Для файла A складываем, а не усредняем координаты двух центров:
Pₓ = 3,6319192 + 6,1168889 = 9,7488081;
Pᵧ = 8,782799 + 24,8122646 = 33,5950636.

Для файла Б проверяем все три пары центров. Расстояние для пары i, j вычисляем как √(xᵢ − xⱼ)² + (yᵢ − yⱼ)²:

Минимальное расстояние даёт пару 2, 3; максимальное — пару 1, 3. Для ответа берём целые части после умножения на 10 000, затем абсолютные величины. Предварительное округление координат центров не допускается.

Распакуем архив и сохраним соответствующие текстовые файлы как A.txt и B.txt рядом с программой. Программа выполняет весь перебор кандидатов:

from math import fsum, hypot, isqrt
from decimal import Decimal

BOXES = [[[1.5, 6, 5.5, 11.5], [3.5, 8, 21.5, 27.5]], [[3, 8, 21.5, 27.5], [6, 11, 31.5, 37.5], [13, 18, 32, 38]]]

def read_points(name):
    with open(name, encoding="utf-8-sig") as f:
        assert f.readline().split() == ["X", "Y"]
        rows = [s.replace(",", ".").split() for s in f if s.strip()]
    return [tuple(int(Decimal(v) * 10**7) for v in row) for row in rows]

def centers(points, boxes, expected_anomalies):
    groups = [[] for box in boxes]
    skipped = 0
    for p in points:
        x, y = p
        found = [i for i, (x1, x2, y1, y2) in enumerate(boxes)
                 if x1 * 10**7 < x < x2 * 10**7 and y1 * 10**7 < y < y2 * 10**7]
        assert len(found) <= 1
        if found:
            groups[found[0]].append(p)
        else:
            skipped += 1
    assert skipped == expected_anomalies
    assert all(groups)
    answer = []
    for group in groups:
        def score(p):
            return fsum(hypot(p[0] - q[0], p[1] - q[1]) for q in group)
        answer.append(min(group, key=score))
    return answer

a = centers(read_points("A.txt"), BOXES[0], 0)
b = centers(read_points("B.txt"), BOXES[1], 3)
print(*(divmod(abs(sum(p[k] for p in a)), 1000)[0] for k in (0, 1)))
squares = [(b[i][0] - b[j][0])**2 + (b[i][1] - b[j][1])**2
           for i in range(3) for j in range(i + 1, 3)]
print(divmod(isqrt(min(squares)), 1000)[0], divmod(isqrt(max(squares)), 1000)[0])

Координаты в программе умножены на 10⁷ и сохранены как целые числа. Это общий положительный масштаб, поэтому точка с минимальной суммой расстояний не меняется. Для ответа по A делим абсолютную сумму на 1000 с отбрасыванием остатка. По Б isqrt вычисляет целую часть квадратного корня точно, после чего целочисленное деление на 1000 даёт требуемые четыре знака без ошибки округления расстояния. Перебор центров занимает O(n₁² + n₂² + n₃²), где nᵢ — размеры кластеров; для файла A слагаемых два.

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

Первая строка ответа: 97488 335950.
Вторая строка ответа: 70853 143630.

Ответ: 97488 335950 70853 143630.