В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям.
По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров — кругов радиуса не более 2 единиц так, что каждая точка попадает ровно в один кластер.
Центром кластера считается та из входящих в него точек, для которой минимально максимальное из расстояний до всех остальных точек кластера.
При этом расстояние вычисляется по стандартной формуле расстояния между точками на евклидовой плоскости.
В файле записан протокол проведения эксперимента. Каждая строка файла содержит два числа: координаты X и Y точки, соответствующей одному испытанию. По данному протоколу надо определить минимальное расстояние между центрами двух различных кластеров.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру.
В ответе запишите два числа: сначала минимальное расстояние между центрами кластеров для файла A, затем для файла B.
В качестве значения указывайте целую часть от умножения найденного числового значения на 10 000.
Ответ:
Построим диаграммы для файла А и Б. Для этого воспользуемся табличным редактором.
Диаграмма для файла А:
Диаграмма для файла Б:
Приведём решение на языке Python для файла А.
import math
f = open('27A.txt')
claster = [[] for i in range(3)]
for s in f:
x,y = [float(c) for c in s.split()]
if y < -2:
claster[0].append ([x,y])
elif x > 4:
claster[1].append ([x,y])
else:
claster[2].append ([x,y])
def cent(cl):
rad = []
for i in cl:
rad.append((sum(math.dist(i,j) for j in cl),i))
return min(rad)[1]
center = [cent(i) for i in claster]
print(center)
mini = float('inf')
for i in range(len(center) - 1):
for j in range(i + 1, len(center)):
mini = min(mini, math.dist(center[i], center[j]))
print(int(mini * 10000))
Приведём решение на языке Python для файла B.
import math
f = open('27B.txt')
claster = [[] for i in range(5)]
for s in f:
x,y = [float(c) for c in s.split()]
if y > 0 and x < -1:
claster[0].append ([x,y])
elif y >1.5 and x < 2:
claster[1].append ([x,y])
elif x > 1.5:
claster[2].append ([x,y])
elif y <-2 and x > 0:
claster[3].append ([x,y])
else:
claster[4].append ([x,y])
def cent(cl):
rad = []
for i in cl:
rad.append((sum(math.dist(i,j) for j in cl),i))
return min(rad)[1]
center = [cent(i) for i in claster]
print(center)
mini = float('inf')
for i in range(len(center) - 1):
for j in range(i + 1, len(center)):
mini = min(mini, math.dist(center[i], center[j]))
print(int(mini * 10000))
Ответ: 86630;35219.