Задача #2954
Анализ данных
(В. Лашин) Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Центроид -это среднее арифметическое положение всех точек на поверхности фигуры. Например, если взять 3 точки (1;2), (3;4) и (5;6), то центроидом будет точка ((1+3+5)/3; (2+4+6)/3) = (3; 4).
В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000. В файле B хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите координаты центроидов, затем вычислите два числа: Px – среднее арифметическое абсцисс центроидов кластеров, и Py – среднее арифметическое ординат центроидов кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px×10000, затем целую часть произведения Py×10000 для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.
Решение
Ответ
from math import dist
clasters = []
eps = 1
for point in open('27B.txt'):
point = list(map(float, point.replace(',', '.').split()))
clasters.append([point])
for claster in clasters[:-1]:
if any(dist(point, claster_point) < eps for claster_point in claster):
clasters[-1] += claster
clasters.remove(claster)
def centroid(claster):
sum_x = sum_y = 0
for x, y in claster:
sum_x += x
sum_y += y
average_x = sum_x / len(claster)
average_y = sum_y / len(claster)
return [average_x, average_y]
centroids = [centroid(claster) for claster in clasters]
# print(len(clasters))
print(abs(int(sum(x for x, y in centroids) / len(centroids) * 10000)), end=' ')
print(abs(int(sum(y for x, y in centroids) / len(centroids) * 10000)))