Присоединиться

11 класс·высокий уровень

Учёный решил провести кластеризацию некоторого множества звёзд по их

Условие

Рисунок к задаче

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид, — это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками A(x1,y1)A ( x_1, y_1 ) и B(x2,y2)B ( x_2, y_2 ) вычисляется по формуле: d(A,B)=(x1−x2)2+(y1−y2)2d ( A, B ) = \sqrt{( x_1 - x_2 )^{2} + ( y_1 - y_2 )^{2}} Даны два входных файла (файл 27A и файл 27 Б). В файле 27A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: координата x, затем координата y (в условных единицах). Известно, что количество звёзд не превышает 1000. В файле 27Б хранятся данные о звёздах трёх кластеров.

Файл 27А.txtФайл 27Б.txtИзвестно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле 27Б аналогична файлу 27А. Возможные данные одного из файлов иллюстрированы графиком.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Pₓ — среднее арифметическое абсцисс центров кластеров, и P_y — среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения Pₓ × 10 000, затем целую часть произведения P_y × 10 000 для файла 27А, во второй строке — аналогичные данные для файла 27Б. Ответ:

Ответ

Ответ и полный разбор откроются после входа

Посмотреть ответ

Решение по шагам

  1. Как рассуждать

    Решение. ##from math import distdata = []# Для А/Бfor s in open('27Б.txt'): x, y = [float(d) for d in s.replace(',', '.').split()] data.append([x, y]) rast = 0.1clusters = []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) #print(*[len(cl) for cl in clusters]) # - проверяет кол-во кластеров# 2 кластера для файла A и 3 для файла B# В случае противоречия меняем rast - это значение (Для A - rast = 1, для B - rast = 0.

    1. def centroid(cl): m = [] for p in cl: s = 0 for p1 in cl: s += dist(p, p1) m.append([s, p]) return min(m)[1] cen = [centroid(cl) for cl in clusters]px = sum(x for x, y in cen)/len(cen)py = sum(y for x, y in cen)/len(cen) print(int(px10000), int(py10000)) Ответ для A: 51318 7467.Ответ для B: 62068

Осталось ещё 2 шага

  1. Приведём решение Сергея Донец на языке…

  2. : cl.MinBy(p -> cl.Sum(q -> Distance(p…

Получить полное решение

Бесплатно · займёт минуту

Другие задачи по теме «Программирование»

Программа получает на вход количество чисел в последовательности, а9 классПрограмма получает на вход количество чисел в последовательности, а9 классПрограмма получает на вход количество чисел в последовательности, а9 классПрограмма получает на вход количество чисел в последовательности, а9 классПрограмма получает на вход количество чисел в последовательности, а9 класс
Похожая задача?Сфотографируйте своё условие — ИИ разберёт его по шагам так же
Учёный решил провести кластеризацию некоторого множества звёзд по их — решение с объяснением | Lom Ai