N непересекающихся непустых подмножеств (кластеров), таких, что точки
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.Будем называть межкластерным диаметром двух кластеров максимальное расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая — другому. Для каждой пары кластеров гарантируется, что межкластерный диаметр образует единственная пара точек. Расстояние между двумя точками на плоскости A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле: В файле A хранятся данные о звёздах двух кластеров, где H = 6, W = 5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.В файле Б хранятся данные о звёздах трёх кластеров, где H = 6, W = 5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Файл АФайл БСтруктура хранения информации о звёздах в файле Б аналогична структуре в файле A.Известно, что в файле Б имеются координаты ровно четырёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти четыре точки не относятся ни к одному из кластеров, их учитывать не нужно.Для обоих файлов определите межкластерные диаметры для каждой пары различных кластеров. Для файла А найдите два числа: Pₓ — модуль разности абсцисс точек, образующих межкластерный диаметр и P_y - сумму ординат точек, образующих межкластерный диаметр. Для файла Б найдите два числа: Q₁ — сумму всех межкластерных диаметров и Q₂ — максимальное расстояние от какой-либо точки, образующей межкластерный диаметр, до точки с координатами (1, 1). В ответе запишите четыре числа: в первой строке - сначала целую часть произведения Pₓ × 1000, затем целую часть абсолютного значения произведения P_y × 1000; во второй строке - сначала целую часть произведения Q₁ × 100, затем целую часть произведения Q₂ × 100. Возможные данные одного из файлов иллюстрированы графиком.Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.Для выполнения задания используйте данные из прилагаемого файла.
Ответ:
Ответ
21549194671402018
Решение по шагам
Как рассуждать
Решение. ##Приведём решение на языке Python для файла А.from math import distdata = [] for s in open('27a.txt'): x, y = [float(d) for d in s.replace(',', '.').split()] data.append([x, y])rast = 2clusters = []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]) *1000Py = abs((mez_diam[1][1] + mez_diam[2][1]) 1000)print(int(Px), int(Py)) Приведём решение на языке Python для файла Б.from math import distdata = []for s in open('27b.txt'): x, y = [float(d) for d in s.replace(',', '.').split()] data.append([x, y])rast = 3clusters = []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.
Осталось ещё 1 шаг — откроются после входа:
- Полный разбор с проверкой ответа
Бесплатно · займёт минуту