27. Демо_2026. Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров. Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.
Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости, которое вычисляется по формуле:
d(A,B) = √((x2 − x1)^2 + ( y2 − y1)^2) .
В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px – минимальную из абсцисс центров кластеров и Py – минимальную из ординат центров кластеров.
Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 – расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 – максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров.
Гарантируется, что во всех кластерах количество точек различно. В ответе запишите четыре числа: в первой строке – сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке – сначала
целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.
Возможные данные одного из файлов проиллюстрированы графиком.
y=9
from math import dist
def f_01( x, y ): # функция распределения по кластерам
if y<9: return 0
else: return 1
k = 2 # количество кластеров
klas = [ [] for i in range(k) ] #массив точек по кластерам
for s in open("DEMO_27_A.txt"):
x, y = map(float,s.replace(',','.').split())
klas[f_01(x,y)].append( (x, y) )
cent = [] # центроиды
for i in range(k):
mSd = float('inf') #мин. сум. рас. больше 10**18
for pC in klas[i]: # цикл по точкам - центрам
sumD = sum( dist(pC,p) for p in klas[i] )
if sumD < mSd:
mSd = sumD; cen = pC
cent.append( cen )
s0=[min(x) for x in zip(*cent)]
print( int(s0[0]*10000), int(s0[1]*10000))
#граф. изобр. распределения точек
from turtle import *
tracer(0); up()
hideturtle()
colors = ['red', 'green', 'blue', 'magenta']
scale, shiftX, shiftY = 25, 150, 150
for i, cluster in enumerate(klas):
for x, y in cluster:
goto( x*scale-shiftX, y*scale-shiftY )
dot( 3, colors[i] )
done()
Для файла А
Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px – минимальную из абсцисс центров кластеров и Py – минимальную из ординат центров кластеров.
Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 – расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 – максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров.
Гарантируется, что во всех кластерах количество точек различно. В ответе запишите четыре числа: в первой строке – сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке – сначала
целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.
Возможные данные одного из файлов проиллюстрированы графиком.
y=27
y=19
y=11
x=19
аномалии
from math import dist
def f_01( x, y ): # функция распределения по кластерам (+1 аном.)
if x>19 and y<27: return 0
elif x<19 and y<27 and y>19: return 1
elif x<19 and y<19 and y>11: return 2
else: return 3
k = 3 # количество кластеров
klas = [ [] for i in range(k+1) ] #массив точек по кластерам (+1 аном.)
for s in open("DEMO_27_B.txt"):
x, y = map(float,s.replace(',','.').split())
klas[f_01(x,y)].append( (x, y) )
cent = [] # центроиды
for i in range(k):
mSd = float('inf') #мин. сум. рас.
for pC in klas[i]: # цикл по точкам – цент.
sumD = sum( dist(pC,p) for p in klas[i] )
if sumD < mSd:
mSd = sumD; cen = pC
cent.append( cen )
m1=0; m2=10**10
n1=-1; n2=-1 #номера клас. мак. мин. кол. точек
for i in range(k):
if len(klas[i])>m1: m1=len(klas[i]); n1=i
if len(klas[i])<m2: m2=len(klas[i]); n2=i
print( int(dist(cent[n1],cent[n2])*10000))
ms = 0 #мак. сум. рас.
for i in range(k):
td = max( dist(cent[i],p) for p in klas[i] )
if td > ms: ms = td
print(int(ms*10000))
Для файла Б
аномалии
Для файла Б