(№ 8078) (Досрочный ЕГЭ-2025) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками A(x1, y1) и B(x2, y2) вычисляется по формуле:
Даны два входных файла (файл A и файл Б). В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (в условных единицах). Известно, что количество звёзд не превышает 1000. В файле Б хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px×10 000, затем целую часть произведения Py×10 000 для файла А, во второй строке – аналогичные данные для файла Б.
from math import dist
f = open("27a.txt")
clusters = [[], []]
for i in f:
x, y = map(float, i.replace(",", ".").split())
if y > 0:
clusters[0].append([x, y])
else:
clusters[1].append([x, y])
sy = sx = 0
for cluster in clusters:
mn = 100000000000000
star = []
for i in cluster:
sm = 0
for j in cluster:
sm += dist(i, j)
if sm < mn:
mn = sm
star = i
sx += star[0]
sy += star[1]
print(int(sx * 10000 / 2), int(sy * 10000 / 2))
from math import dist
f = open("27b.txt")
clusters = [[], [], []]
for i in f:
x, y = map(float, i.replace(",", ".").split())
if x < 0:
clusters[0].append([x, y])
elif y > 0:
clusters[1].append([x, y])
else:
clusters[2].append([x, y])
sy = sx = 0
for cluster in clusters:
mn = 100000000000000
star = []
for i in cluster:
sm = 0
for j in cluster:
sm += dist(i, j)
if sm < mn:
mn = sm
star = i
sx += star[0]
sy += star[1]
print(int(sx * 10000 / 3), int(sy * 10000 / 3))