Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид, — это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками
и 
вычисляется по формуле: 
Даны два входных файла (файл 27A и файл 27Б). В файле 27A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: координата x, затем координата y (в условных единицах). Известно, что количество звёзд не превышает 1000. В файле 27Б хранятся данные о звёздах трёх кластеров.
Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле 27Б аналогична файлу 27А. Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px — среднее арифметическое абсцисс центров кластеров, и Py — среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px × 10 000, затем целую часть произведения Py × 10 000 для файла 27А, во второй строке — аналогичные данные для файла 27Б.
Ответ:
Приведём решение на языке Python.
from math import dist
data = []
# Для А/Б
for s in open('27Б.txt'):
x, y = [float(d) for d in s.replace(',', '.').split()]
data.append([x, y])
rast = 0.1
clusters = []
while data:
cl = [data.pop()]
for p in cl:
sosed = [p1 for p1 in data if dist(p, p1) < rast]
for p1 in sosed:
cl.append(p1)
data.remove(p1)
clusters.append(cl)
#print(*[len(cl) for cl in clusters]) # - проверяет кол-во кластеров
# 2 кластера для файла A и 3 для файла B
# В случае противоречия меняем rast - это значение (Для A - rast = 1, для B - rast = 0.1)
def centroid(cl):
m = []
for p in cl:
s = 0
for p1 in cl:
s += dist(p, p1)
m.append([s, p])
return min(m)[1]
cen = [centroid(cl) for cl in clusters]
px = sum(x for x, y in cen)/len(cen)
py = sum(y for x, y in cen)/len(cen)
print(int(px*10000), int(py*10000))
Ответ для A: 32055 58097.
Ответ для B: 31886 25834.