В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям.
По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров — прямоугольников 
Центроидом кластера называется та из входящих в него точек, для которой минимальна сумма расстояний до всех остальных точек кластера.
Обработка результатов эксперимента включает следующие шаги:
1) кластер, содержащий наименьшее число точек, исключается;
2) определяются центроиды всех оставшихся кластеров;
3) для найденных центроидов вычисляется средняя точка.
Средней для группы точек называется точка (не обязательно входящая в группу), координаты которой определяются как средние арифметические значения координат всех точек группы.
В файле записан протокол проведения эксперимента. Каждая строка файла содержит два числа: координаты X и Y точки, соответствующей одному испытанию. По данному протоколу надо определить среднюю точку центроидов всех кластеров за исключением содержащего наименьшее число точек.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. По данным каждого из представленных файлов определите координаты средней точки по описанным выше правилам.
В ответе запишите четыре числа: сначала (в первой строке) координаты X и Y средней точки для файла A, затем (во второй строке) координаты X и Y средней точки для файла B.
В качестве значения координаты указывайте целую часть от умножения числового значения координаты на 10 000.
Ответ:
Построим диаграммы для файла А и Б. Для этого воспользуемся табличным редактором.
Для файла А:
Для файла Б:
Диаграмма для файла А:
Диаграмма для файла Б:
Приведём решение на языке Python для файла А.
f = open('27A.txt')
m = []
claster = [[] for i in range(3)]
for s in f:
x,y = [float(c) for c in s.split()]
m.append([x,y])
if -1 <= x <=2 and 6<= y <=9:
claster[0].append ([x,y])
if 0 <= x <= 3 and 3<= y <=6:
claster[1].append ([x,y])
if -1.5 <= x <= 0.5 and -1<= y <=2:
claster[2].append ([x,y])
def centroid(claster):
maxi = 10**10
maxix, maxiy = 0,0
for x1,y1 in claster:
d = 0
for x2,y2 in claster:
d += ((x2-x1)**2 + (y2-y1)**2)** 0.5
if d < maxi:
maxi,maxix,maxiy = d, x1, y1
return maxix, maxiy
mini = min(len(i) for i in claster)
claster = [j for j in claster if len(j)!= mini]
center = [centroid(n) for n in claster]
sumx, sumy = 0, 0
for x,y in center:
sumx += x
sumy += y
otv1, otv2 = int(sumx*10000/len(center)), int(sumy*10000/len(center))
print(otv1, otv2)
Приведём решение на языке Python для файла Б.
f = open('27B.txt')
m = []
claster = [[] for i in range(5)]
for s in f:
x,y = [float(c) for c in s.split()]
m.append([x,y])
if -2.5 <= x <=0.5 and -1.5<= y <=1.5:
claster[0].append ([x,y])
if -0.5 <= x <= 2.5 and 3<= y <=5.5:
claster[1].append ([x,y])
if 4 <= x <= 7 and 5<= y <=8:
claster[2].append ([x,y])
if 3.5 <= x <= 6.5 and 1.5<= y <=4.5:
claster[3].append ([x,y])
if 3 <= x <= 6.5 and -2.5<= y <=1.5:
claster[4].append ([x,y])
def centroid(claster):
maxi = 10**10
maxix, maxiy = 0,0
for x1,y1 in claster:
d = 0
for x2,y2 in claster:
d += ((x2-x1)**2 + (y2-y1)**2)** 0.5
if d < maxi:
maxi,maxix,maxiy = d, x1, y1
return maxix, maxiy
mini = min(len(i) for i in claster)
claster = [j for j in claster if len(j)!= mini]
center = [centroid(n) for n in claster]
sumx, sumy = 0, 0
for x,y in center:
sumx += x
sumy += y
otv1, otv2 = int(sumx*10000/len(center)), int(sumy*10000/len(center))
print(otv1, otv2)
В результате работы данного алгоритма при вводе данных из
Приведём решение Юрия Красильникова на языке Python.
def centroid(cluster):
sumdist = [sum([dist(star1,star2) for star1 in cluster]) for star2 in cluster]
return cluster[sumdist.index(min(sumdist))]
from math import dist
f = open('27A.csv')
f.readline() # Читаем (и игнорируем) строку с заголовками столбцов (X Y).
stars = [tuple(map(float,s.replace(',','.').split(';'))) for s in f]
radius = 0.5
clusters = []
while stars:
cluster = [stars.pop()]
for c in cluster:
near = [s for s in stars if dist(c,s) < radius]
cluster += near
for n in near: stars.remove(n)
clusters.append(cluster)
print('кластеров:',len(clusters),'; точек:',*[len(c) for c in clusters])
clen=[len(c) for c in clusters]
del clusters[clen.index(min(clen))]
centers = [centroid(c) for c in clusters]
answer = [int(sum([c[i] for c in centers]) / len(centers) * 10000) for i in range(2)]
print( *answer )