Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Диаметром кластера назовём максимальное расстояние между двумя точками в кластере. Для каждого кластера гарантируется, что диаметр образует единственная пара точек. Расстояние между двумя точками на плоскости A(x1; y1) и B(x2; y2) вычисляется по формуле:
В файле А хранятся данные о звёздах двух кластеров, где H = 3, W = 4 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H = 6, W = 5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звёздах в файле Б аналогична файлу А.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А найдите пары точек, которые образуют диаметр каждого кластера. Затем вычислите два числа: Px — минимальную из сумм абсцисс этих точек для всех кластеров и Py — минимальную из сумм ординат этих точек для всех кластеров. Для файла Б найдите два числа: Q1 — диаметр кластера с минимальным количеством точек и Q2 — максимальное расстояние от точки, образующей диаметр одного кластера, до точки, образующей диаметр другого кластера.
Гарантируется, что во всех кластерах количество точек различно.
В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютного значения произведения Px × 10 000, затем целую часть абсолютного значения произведения Py × 10 000; во второй строке — сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.
Ответ:
Построим диаграммы для файла А и Б. Для этого воспользуемся табличным редактором.
Диаграмма для файла А:
Диаграмма для файла Б:
Приведём решение на языке Python для файла А.
from math import dist
f = open('27A.txt')
claster = [[] for i in range(2)]
for s in f:
x,y= map(float, s.split())
if x < 19:
claster[0].append((x,y))
else:
claster[1].append((x,y))
def diam(claster):
rad = []
for i in claster:
for j in claster:
rad.append([dist(i,j),[i,j]])
return max(rad)[1]
centr = [diam(i) for i in claster]
p1, p2 = centr[0]
p3, p4 = centr[1]
print(min((p1[0] + p2[0], p1[1] + p2[1]))*10000)
print(min((p3[0] + p4[0], p3[1] + p4[1]))*10000)
Приведём решение на языке Python для файла В.
from math import dist
f = open('27B.txt')
claster = [[] for i in range(3)]
for s in f:
x,y= map(float, s.split())
if x > 20 and y > 25:
claster[0].append((x,y))
elif x < 0 and 10 > y > 5:
claster[1].append((x,y))
elif x < 0 and y < 0:
claster[2].append((x,y))
def diam(claster):
rad = []
for i in claster:
for j in claster:
rad.append([dist(i,j),[i,j]])
return max(rad)
D = [diam(i)[1] for i in claster]
k_c = [len(i) for i in claster]
Q1 = (([diam(i)[0] for i in claster])[k_c.index(min(k_c))])*10000
print(Q1)
Q2 = []
for i in range(len(D) - 1):
for j in range(i + 1, len(D)):
for p1 in D[i]:
for p2 in D[j]:
Q2.append(dist(p1,p2)*10000)
print(max(Q2))
Ответ: 145015 313020 29254 488624.
Приведём решение Юрия Красильникова на языке Python.
ffrom math import dist # dist работает гораздо быстрее, чем (x**2+y**2)**0.5
границыА = [[5,19,10,25],[20,12,25,20]]
границыБ = [[-10,-7,0,0],[-10,5,0,10],[25,25,35,35]]
# границы содержат для каждого кластера список [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 диаметр(кластер):
макс_р = 0
for зв1 in кластер:
for зв2 in кластер:
д = dist(зв1,зв2)
if д > макс_р:
макс_р = д
ответ = [зв1,зв2]
return ответ
f=open('27A.txt')
print('Задача А:')
звезды = [list(map(float,s.replace(',','.').split())) for s in f]
кластеры = кластеризация(звезды,границыА)
диаметры = [диаметр(к) for к in кластеры]
px = int(min(диаметры[0][0][0]+диаметры[0][1][0],диаметры[1][0][0]+диаметры[1][1][0])*10000)
py = int(min(диаметры[0][0][1]+диаметры[0][1][1],диаметры[1][0][1]+диаметры[1][1][1])*10000)
print(px, py)
f=open('27B.txt')
print('Задача Б:')
звезды = [list(map(float,s.replace(',','.').split())) for s in f]
кластеры = кластеризация(звезды,границыБ)
кластеры.sort(key=lambda x: len(x)) # по количеству точек
диаметры = [диаметр(к) for к in кластеры]
qx = int(dist(диаметры[0][0],диаметры[0][1])*10000)
расстояния = []
for д1 in range(len(диаметры)-1):
for д2 in range(д1+1,len(диаметры)):
for n1 in range(2):
for n2 in range(2):
расстояния.append(dist(диаметры[д1][n1],диаметры[д2][n2]))
qy = int(max(расстояния)*10000)
print(qx,qy)