Задание 27. Информатика. ЕГЭ. Статград. Профиль. 12.05.2025-1

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

По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров так, что каждая точка попадает ровно в один кластер, при этом ближайшие точки разных кластеров отстоят друг от друга не менее, чем на единичное расстояние.

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

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

from math import dist

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

for task in (0, 1):
    data = [tuple(map(float, line.split())) for line in open(files[task])]
    eps = 1
    clusters = []
    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(cl) for cl in clusters])
    max_points = []
    for cl in clusters:
        nmax = 0
        ptmp = None
        for p in cl:
            n = len([pt for pt in cl if dist(p, pt) < eps])
            if n > nmax:
                nmax = n
                ptmp = p
            elif n == nmax and ptmp[0] < p[0]:
                ptmp = p

        max_points.append(ptmp)
    min_dist = float('inf')
    for i in range(len(max_points) - 1):
        for j in range(i + 1, len(max_points)):
            min_dist = min(min_dist, dist(max_points[i], max_points[j]))
    print(int(min_dist * 10_000))