Задание №88375. Учёный решил провести кластеризацию некоторого множества звёзд

Задание №88375 ЕГЭ Информатике

Условие задания #88375

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

Истинный центр кластера, или центроид,  — это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x₁, y₁) и B(x₂, y₂) на плоскости, которое вычисляется по формуле:

$d (A, B) = \sqrt{({(x_{2} - x_{1})}^{2} + {(y_{2} - y_{1})}^{2})}$

В файле A хранятся данные о звёздах двух кластеров, где H  =  3, W  =  3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле Б хранятся данные о звёздах трёх кластеров, где H  =  3, W  =  3 для каждого кластера. Известно, что количество звёзд не превышает 10 000.

Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: P_x  — среднее арифметическое абсцисс центров кластеров, и P_y  — среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения P_x × 10 000 , затем целую часть произведения P_y × 10 000 для файла А, во второй строке  — аналогичные данные для файла Б.

27-3a.txt 27-3b.txt

Ответ

Ответ:

32055 58097 31886 25834

Решение

Файл A

K = 2 # количество кластеров

def findClusterNo( x, y ):
return 0 if x < 3 else 1

#------------------------------------------------

clusters = [ [] for i in range(K) ]

for s in open("27-3a.txt"):
x, y = s.replace(',','.').split()
x, y = float(x), float(y)
clusterNo = findClusterNo( x, y )
clusters[clusterNo].append( (x, y) )

import math
def dist( p1, p2 ):
#return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
return math.hypot( p1[0] - p2[0], p1[1] - p2[1] )

centers = []
for k in range(K):
minSumDist = float('inf')
for pCenter in clusters[k]:
sumDist = sum( dist(pCenter,p)
for p in clusters[k] )
if sumDist < minSumDist:
minSumDist = sumDist
center = pCenter
centers.append( center )

print( "Центроиды:\n", centers )

sumX, sumY = 0, 0
for k in range(K):
sumX += centers[k][0]
sumY += centers[k][1]

print( int(sumX/K*10000), int(sumY/K*10000) )

Файл B

K = 3 # количество кластеров

def findClusterNo( x, y ):
return 0 if x > 4 else \
1 if y > 2 else \
2