Задание 27. Информатика. ЕГЭ. Статград. 04.03.2025
- Просмотры: 410
- Изменено: 7 марта 2025
В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям.
По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров — кругов радиуса не более \(2\) единиц так, что каждая точка попадает ровно в один кластер. Центром кластера считается та из входящих в него точек, для которой минимально максимальное из расстояний до всех остальных точек кластера. При этом расстояние вычисляется по стандартной формуле расстояния между точками на евклидовой плоскости.
В файле записан протокол проведения эксперимента. Каждая строка файла содержит два числа: координаты \(X\) и \(Y\) точки, соответствующей одному испытанию. По данному протоколу надо определить минимальное расстояние между центрами двух различных кластеров.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе запишите два числа: сначала минимальное расстояние между центрами кластеров для файла A, затем для файла B. В качестве значения указывайте целую часть от умножения найденного числового значения на \(10~000.\)
Решение:
Python
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))
Ответ: \(86689 \,\, 33893\)