N непересекающихся непустых подмножеств (кластеров), таких что точки
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Диаметром кластера назовём максимальное расстояние между двумя точками в кластере. Для каждого кластера гарантируется, что диаметр образует единственная пара точек. Расстояние между двумя точками на плоскости A(x₁; y₁) и B(x₂; y₂) вычисляется по формуле: В файле А хранятся данные о звёздах двух кластеров, где H = 3, W = 4 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.В файле Б хранятся данные о звёздах трёх кластеров, где H = 6, W = 5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звёздах в файле Б аналогична файлу А.Файл АФайл БИзвестно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А найдите пары точек, которые образуют диаметр каждого кластера. Затем вычислите два числа: Pₓ — минимальную из сумм абсцисс этих точек для всех кластеров и P_y — минимальную из сумм ординат этих точек для всех кластеров. Для файла Б найдите два числа: Q₁ — диаметр кластера с минимальным количеством точек и Q₂ — максимальное расстояние от точки, образующей диаметр одного кластера, до точки, образующей диаметр другого кластера.
Гарантируется, что во всех кластерах количество точек различно.В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютного значения произведения Pₓ × 10 000, затем целую часть абсолютного значения произведения P_y × 10 000; во второй строке — сначала целую часть произведения Q₁ × 10 000, затем целую часть произведения Q₂ × 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))])*10000print(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))
Осталось ещё 1 шаг
Приведём решение Юрия Красильникова на языке…
Бесплатно · займёт минуту