Задание 27. Информатика. ЕГЭ. Статград. 04.03.2025

В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям.

По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров — кругов радиуса не более \(2\) единиц так, что каждая точка попадает ровно в один кластер. Центром кластера считается та из входящих в него точек, для которой минимально максимальное из расстояний до всех остальных точек кластера. При этом расстояние вычисляется по стандартной формуле расстояния между точками на евклидовой плоскости.

В файле записан протокол проведения эксперимента. Каждая строка файла содержит два числа: координаты \(X\) и \(Y\) точки, соответствующей одному испытанию. По данному протоколу надо определить минимальное расстояние между центрами двух различных кластеров.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе запишите два числа: сначала минимальное расстояние между центрами кластеров для файла A, затем для файла B. В качестве значения указывайте целую часть от умножения найденного числового значения на \(10~000.\)

from math import dist

base = ''
files = ['27A.txt', '27B.txt']

for task in (0, 1):
    data = [tuple(map(float, line.replace(',', '.').split())) for line in open(base + files[task])]
    clusters = []
    eps = 1
    while data:
        clusters.append([data.pop()])
        for p in clusters[-1]:
            neigh = [pt for pt in data if dist(p, pt) < eps]
            clusters[-1] += neigh
            for pt in neigh:
                data.remove(pt)

    #print(len(clusters), [len(c) for c in clusters])
    centers = []
    for cl in clusters:
        dmin = float('inf')
        c = None
        for p in cl:
            d = max(dist(p, pt) for pt in cl)
            if d < dmin:
                dmin = d
                c = p
        centers.append(c)

    min_center = float('inf')
    for i in range(len(centers) - 1):
        for j in range(i + 1, len(centers)):
            min_center = min(min_center, dist(centers[i], centers[j]))
    print(int(min_center * 10_000))