Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть антицентром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера максимальна. Для каждого кластера гарантируется единственность его антицентра. Расстояние между двумя точками А (х1, y1) и B (х2, y2) на плоскости вычисляется по формуле:
В файле А хранятся координаты точек двух кластеров, где Н = 8, W = 4 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата х, затем координата у. Значения даны в условных единицах. Известно, что количество точек не превышает 1000.
В файле Б хранятся координаты точек трёх кластеров, где Н = 6, W = 7 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации о звёздах в файле Б аналогична структуре в файле А.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А определите координаты антицентра каждого кластера, затем вычислите два числа: P1 — сумма абсциссы и ординаты антицентра кластера с наименьшим количеством точек, и P2 — сумма абсциссы и ординаты антицентра кластера с наибольшим количеством точек. Гарантируется, что во всех кластерах количество точек различно.
Для файла Б определите координаты антицентра каждого кластера, затем вычислите два числа: Qx — абсциссу наиболее отдалённого антицентра кластера от начала координат, и Qy — ординату ближайшего антицентра кластера к началу координат.
В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения P1 × 10 000, затем целую часть абсолютной величины произведения P2 × 10 000; во второй строке — сначала целую часть произведения Qx × 10 000, затем целую часть произведения Qy × 10 000.
Возможные данные одного из файлов проиллюстрированы графиком.
Ответ:
Построим диаграммы для файла А и Б. Для этого воспользуемся табличным редактором.
Диаграмма для файла А:
Диаграмма для файла Б:
Приведём решение на языке Python для файла А.
from math import *
f = open('27.txt')
claster = [[] for i in range(2)]
for s in f:
x,y= map(float, s.split())
if y < 90:
claster[0].append((x,y))
else:
claster[1].append((x,y))
def centroid(claster):
rad = []
for i in claster:
rad.append((sum(dist(i,j) for j in claster),i))
return max(rad)[1]
len_claster = sorted(claster, key = len )
centr = [centroid(i) for i in len_claster]
P1 = sum(centr[0]) *10000
P2 = sum(centr[1]) *10000
print(int(abs(P1)), int(abs(P2)))
Приведём решение на языке Python для файла В.
from math import *
f = open('27.txt')
claster = [[] for i in range(3)]
for s in f:
x,y= map(float, s.split())
if x > 16 and 32 > y > 24:
claster[0].append((x,y))
elif x > 16 and 41 > y > 33:
claster[1].append((x,y))
elif x > 16 and 50 > y > 42:
claster[2].append((x,y))
def centroid(claster):
rad = []
for i in claster:
rad.append((sum(dist(i,j) for j in claster),i))
return max(rad)[1]
centr = [centroid(i) for i in claster]
Qx = max([(dist(i, (0,0)), i) for i in centr])[1][0]
Qy = min([(dist(i, (0,0)), i) for i in centr])[1][1]
print(int(abs(Qx*10000)), int(abs(Qy*10000)))
Ответ: 1126711 1517181 213883 264132.
Приведём решение Юрия Красильникова на языке Python.
from math import dist # dist работает гораздо быстрее, чем (x**2+y**2)**0.5
границыА = [[10,94,30,100],[60,82,80,90]]
границыБ = [[10,20,30,33],[10,33,30,42],[10,42,30,52]]
# границы содержат для каждого кластера список [Xmin,Ymin,Xmax,Ymax]
# Чтобы составить списки, нужно открыть файл в LibreOffice Calc, построить диаграмму X-Y
# и визуально определить границы координат для каждого кластера.
def кластеризация(звезды,границы):
кластеры=[[] for _ in range(len(границы))]
for x,y in звезды:
внутри = [xmin <= x <= xmax and ymin <= y <= ymax for xmin,ymin,xmax,ymax in границы]
if sum(внутри) == 1: кластеры[внутри.index(True)].append([x,y])
elif sum(внутри) == 0: print('Звезда',[x,y],'вне кластеров')
else: print('Ошибка: неоднозначные границы')
print('Кластеров:',len(кластеры),'звезд:',*[len(x) for x in кластеры])
return кластеры
def антицентр(кластер):
суммы = [sum(dist(звезда1,звезда2) for звезда2 in кластер) for звезда1 in кластер]
return кластер[суммы.index(max(суммы))] # для центра заменить max на min
f=open('27A.txt')
f.readline() # пропускаем заголовки столбцов
print('Задача А:')
звезды = [list(map(float,s.replace(',','.').split())) for s in f]
кластеры = кластеризация(звезды,границыА)
кластеры.sort(key=lambda x: len(x)) # по количеству звезд
антицентры = [антицентр(к) for к in кластеры]
px = int(sum(антицентры[0])*10000) # самый малочисленный
py = int(sum(антицентры[1])*10000) # самый многочисленный
print(px, py)
f=open('27B.txt')
f.readline() # пропускаем заголовки столбцов
print('Задача Б:')
звезды = [list(map(float,s.replace(',','.').split())) for s in f]
кластеры = кластеризация(звезды,границыБ)
антицентры = [антицентр(к) for к in кластеры]
антицентры.sort(key=lambda x: dist(x,(0,0))) # по удаленности от начала координат
qx = int(антицентры[-1][0]*10000) # абсцисса самого дальнего
qy = int(антицентры[0][1]*10000) # ордината самого ближнего
print(qx,qy)