Задание 27 ЕГЭ по информатике

Question

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть медианой по $x$ такую точку, что половина (кроме самой точки) точек по значению абсциссы будет больше её абсциссы, а половина меньше. А медианой по $y$ аналогичное значение в ординатах. Гарантируется единственной такого значения в каждом кластере. Так же гарантируется, что в каждом кластере нечётное количество точек.
В файле A хранятся данные о звёздах двух кластеров, где $H=3$, $W=3$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где $H=3$, $W=3$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите координаты медиан по $x$ и медиан по $y$, затем вычислите два числа: $P_x$​ – среднее арифметическое абсцисс медиан по х кластеров, и $P_y$​ – среднее арифметическое ординат медиан по y кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x*10000$, затем целую часть произведения $P_y*10000$ для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов проиллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов.
Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20207_27A_2.txt
Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20207_27B_2.txt

Accepted Answer

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)))

Задание 27 ЕГЭ по информатике

Кластеризация