Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, — это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости, которое вычисляется по формуле:
В файле A хранятся данные о звёздах двух кластеров, где H = 3, W = 3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H = 3, W = 3 для каждого кластера. Известно, что количество звёзд не превышает 10 000.
Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px — среднее арифметическое абсцисс центров кластеров, и Py — среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px × 10 000 , затем целую часть произведения Py × 10 000 для файла А, во второй строке — аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.
Ответ:
Приведём решение на языке Python.
f = open('demo_2025.txt')
f.readline()
ans = []
min_summ = 10**10
stars = [list(map(float, s.replace(',','.').split())) for s in f]
for i in range (len(stars) - 1):
for j in range(i+1, len (stars) - 1):
center1 = stars[i]
center2 = stars[j]
summ = 0
for star in stars:
d1 = ((star[0] - center1[0]) ** 2 + (star[1] - center1[1]) ** 2)**0.5
d2 = ((star[0] - center2[0]) ** 2 + (star[1] - center2[1]) ** 2)**0.5
summ += min(d1, d2)
if summ < min_summ:
min_summ = summ
ans = [center1, center2]
print((ans[0][0] + ans[1][0]) / 2 * 10000, (ans[0][1] + ans[1][1]) / 2 * 10000)
Ответ:
10738 30730
37522 51277
Приведём решение Юрия Красильникова на языке Python.
def centroid(cluster):
sd=[sum([((c1[0]-c2[0])**2+(c1[1]-c2[1])**2)**0.5 for c1 in cluster]) for c2 in cluster]
return cluster[sd.index(min(sd))]
f=open('demo_2025_27_Б.txt')
f.readline() # Читаем строку с заголовками столбцов
stars=[list(map(float,s.replace(',','.').split())) for s in f]
# borders=[[-2,1,-1,3],[1,5,3,7]] # для файла A
borders=[[-1,3,0,3],[2,5,7,11],[5,8,4,7]] # для файла B
clusters=[[] for _ in range(len(borders))] # список из len(borders) пустых подсписков
for s in stars:
tf=[b[0] < s[0] < b[1] and b[2] < s[1] < b[3] for b in borders]
if sum(tf)!=1: print('Ошибка кластеризации', s, tf)
clusters[tf.index(True)].append(s)
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)
Приведём решение Юрия Красильникова на языке Python.
def centroid(cluster):
sumdist = [sum([dist(star1,star2) for star1 in cluster]) for star2 in cluster]
return cluster[sumdist.index(min(sumdist))]
# функция dist работает в несколько раз быстрее, чем выражение
# ((star1[0] - star2[0])**2 + (star1[1] - star2[1])**2)**0.5
from math import dist
f = open('demo_2025_27_Б.txt')
f.readline() # Читаем (и игнорируем) строку с заголовками столбцов (X Y).
stars = [tuple(map(float,s.replace(',','.').split())) for s in f]
# Переменная radius - это радиус круга, внутри которого находятся точки,
# присоединяемые к кластеру. Она должна быть меньше, чем минимальное расстояние
# между звёздами разных кластеров, но больше, чем максимальное расстояние между
# звёздами одного кластера.
radius = 1.0
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)
# Результат кластеризации: количество кластеров и их размеры.
# Если кластеров больше, чем в условии, следует увеличить переменную radius,
# если меньше - уменьшить её.
print('кластеров:',len(clusters),'; точек:',*[len(c) for c in clusters])
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)