Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть межкластерным диаметром двух кластеров максимальное расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая — другому. Для каждой пары кластеров гарантируется, что межкластерный диаметр образует единственная пара точек. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле:
В файле A хранятся данные о звёздах двух кластеров, где H = 6, W = 5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H = 6, W = 5 для каждого кластера. Известно, что количество звёзд не превышает 10 000.
Структура хранения информации о звёздах в файле Б аналогична структуре в файле A.
Известно, что в файле Б имеются координаты ровно четырёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти четыре точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для обоих файлов определите межкластерные диаметры для каждой пары различных кластеров. Для файла А найдите два числа: Px — модуль разности абсцисс точек, образующих межкластерный диаметр и Py – сумму ординат точек, образующих межкластерный диаметр. Для файла Б найдите два числа: Q1 — сумму всех межкластерных диаметров и Q2 — максимальное расстояние от какой-либо точки, образующей межкластерный диаметр, до точки с координатами (1, 1).
В ответе запишите четыре числа: в первой строке – сначала целую часть произведения Px × 1000, затем целую часть абсолютного значения произведения Py × 1000; во второй строке – сначала целую часть произведения Q1 × 100, затем целую часть произведения Q2 × 100. Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.
Ответ:
##Приведём решение на языке Python для файла А.
from math import dist
data = []
for s in open('27a.txt'):
x, y = [float(d) for d in s.replace(',', '.').split()]
data.append([x, y])
rast = 2
clusters = []
while data:
cl = [data.pop()]
for p in cl:
sosed = [p1 for p1 in data if dist(p, p1) < rast]
for p1 in sosed:
cl.append(p1)
data.remove(p1)
clusters.append(cl)
clusters.sort(key=len)
def rast_clast(cluster1, cluster2):
res = []
for s1 in cluster1:
for s2 in cluster2:
res.append([dist(s1,s2), s1, s2])
return max(res)
mez_diam = rast_clast(clusters[0], clusters[1])
Px = abs(mez_diam[1][0] - mez_diam[2][0]) *1000
Py = abs((mez_diam[1][1] + mez_diam[2][1]) *1000)
print(int(Px), int(Py))
Приведём решение на языке Python для файла Б.
from math import dist
data = []
for s in open('27b.txt'):
x, y = [float(d) for d in s.replace(',', '.').split()]
data.append([x, y])
rast = 3
clusters = []
while data:
cl = [data.pop()]
for p in cl:
sosed = [p1 for p1 in data if dist(p, p1) < rast]
for p1 in sosed:
cl.append(p1)
data.remove(p1)
if len(cl) >= 2:
clusters.append(cl)
clusters.sort(key=len)
#print(*[len(cl) for cl in clusters]) # - проверяет кол-во кластеров
# 2 кластера для файла A и 3 для файла B
# В случае противоречия меняем rast - это значение
def rast_clast(cluster1, cluster2):
res = []
for s1 in cluster1:
for s2 in cluster2:
res.append([dist(s1,s2), s1, s2])
return max(res)
mez_diam = [rast_clast(clusters[i], clusters[j]) for i in range(len(clusters)) for j in range(i+1, len(clusters))]
Q1 = sum(d[0] for d in mez_diam) *100
Q2 = max(dist(i,[1,1]) for d in mez_diam for i in d[1:]) * 100
print(int(Q1),int(Q2))
Ответ: 21549 1946 7140 2018.