КЕГЕ тип 27 № 18678

 Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор не менее чем из 30 соседних звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками 

$A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле $\mathit{\text{d}}(A,B)=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$.
Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.
В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (в условных единицах). Известно, что количество звёзд не превышает 1000. В файле Б хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x\times 100000$, затем целую часть произведения $P_y\times 100000$ для файла А, во второй строке – аналогичные данные для файла Б.

Файлы к заданию: 27A_18678.txt,   27B_18678.txt (запятые заменены на точки методами текстового редактора Блокнот)

Решение

#Считывание данных из файла

a=[]

for i in open('27B_18678.txt'):

    x,y=[float(c) for c in i.split()]

    a.append([x,y])

print(len(a))

# функция вычисления расстояния между двумя точками

def d(t1,t2):

    x1,y1,x2,y2=*t1,*t2

    return ((x2-x1)**2+(y2-y1)**2)**0.5

def cl(t):

    c=[t1 for t1 in a if d(t,t1)<1]#Собираем в список все точки расстояние с базовой меньше 1

    if len(c)>0:#Если такие есть

        for t1 in c: a.remove(t1) # Удаляем их из общего списка точек

        clas=[cl(t1) for t1 in c]# Для точек из списка c найдем оставшиеся точки

        for j in clas: c.extend(j)# Добавляем найденные точки в окончательный список кластера

    return c

#Раскидаем все точки по кластерам

claster=[] # Список кластеров

while len(a)>0:

    p=a.pop()# Берем последнюю точку в списке точек одновременно удаляя ее из него

    clast=[p]+cl(p)#Формируем кластер

    print(len(clast))# Количество точек кластера -для самоконтроля

    claster.append(clast)# добавляем сформированный кластер в список кластеров

claster=[z for z in claster if len(z)>=30] #удаляем аномалии

#функция центра кластера

def centr(kl):

    r=[] #список расстояний

    for g in kl:

        rt=sum(d(g,g1) for g1 in kl)# находим сумму расстояний от тачки g кластера до всех остальных точек этого кластера

        r.append([rt,g])# сохраняем суммарное расстояние и координаты точки

    return min(r)[1]# возвращаем точку, у которой минимальное суммарное расстояние до остальных точек кластера. Т.е. она центр

# создаем список центров кластеров

centry=[centr(v) for v in claster]

# вывод результата

Px=sum(x for x,y in centry)/len(centry)# среднеарифметическая  координата x   

Py=sum(y for x,y in centry)/len(centry)# среднеарифметическая  координата y   

print(int(Px*100000),int(Py*100000))