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