Задача #2952
Анализ данных
(В. Лашин) Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть медианой по х такую точку, что половина(кроме самой точки) точек по значению абсциссы будет больше её абсциссы, а половина меньше. А медианой по y аналогичное значение в ординатах. Гарантируется единственной такого значения в каждом кластере. Так же гарантируется, что в каждом кластере нечётное количество точек.
В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000. В файле B хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А. Для каждого файла определите координаты медиан по х и медиан по y, затем вычислите два числа: Px – среднее арифметическое абсцисс медиан по х кластеров, и Py – среднее арифметическое ординат медиан по y кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения 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 mediana_x(claster):
for point_1 in claster:
count = 0
for point_2 in claster:
if point_2[0] > point_1[0]:
count += 1
if count == len(claster) // 2:
return point_1[0]
def mediana_y(claster):
for point_1 in claster:
count = 0
for point_2 in claster:
if point_2[1] > point_1[1]:
count += 1
if count == len(claster) // 2:
return point_1[1]
medians_x = [mediana_x(claster) for claster in clasters]
medians_y = [mediana_y(claster) for claster in clasters]
#print(len(clasters))
print(abs(int(sum(medians_x) / len(medians_x) * 10000)))
print(abs(int(sum(medians_y) / len(medians_y) * 10000)))