Задача #2971

Анализ данных

Уровень ЕГЭ

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Точкой наведения назовём точку, в единичном окрестности от которой находится наибольшее количество точек кластера. Если таких точек несколько, то выбирается точка с наибольшей координатой x. Расстояние между двумя точками на плоскости $A (x_{1}, y_{1})$ и $B (x_{2}, y_{2})$ вычисляется по формуле: $d (A, B) = \sqrt{(x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2}}$ .
В файле A хранятся данные о звёздах четырёх кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах семи кластеров, где H=5, W=5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите координаты точки наведения каждого кластера, затем вычислите два числа: $P_{x}$ – среднее арифметическое абсцисс точек наведения кластеров, и $P_{y}$ –среднее арифметическое ординат точек наведения кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения $| P_{x} | \times 100000$ , затем целую часть произведения $| P_{y} | \times 100000$ для файла А, во второй строке – аналогичные данные для файла Б.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.

Для выполнения задания используйте данные из прилагаемого файла.

Файлы к задаче

Скачать 27A.txt Скачать 27B.txt

Вопрос A

Вопрос B

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть

Ответ

Вопрос A

171553

32527

Вопрос B

157853

13516

clustersA = [[] for i in range(4)]
for s in open('27A.txt'):
    x,y = [float(d) for d in s.split()]
    if x<0 and y>0:
        clustersA[0].append([x,y])
    if x<2 and y<0:
        clustersA[1].append([x,y])
    if x>2 and y>2:
        clustersA[2].append([x,y])
    if x>3 and y<1.5:
        clustersA[3].append([x,y])
#print([len(cl) for cl in clustersA])

clustersB = [[] for i in range(7)]
for s in open('27B.txt'):
    x,y = [float(d) for d in s.split()]
    if x>6 and y>3:
        clustersB[0].append([x,y])
    elif x>1 and y>1:
        clustersB[1].append([x,y])
    elif x>6:
        clustersB[2].append([x,y])
    elif x>1:
        clustersB[3].append([x,y])
    elif y<-4:
        clustersB[4].append([x,y])
    elif x<-4:
        clustersB[5].append([x,y])
    else:
        clustersB[6].append([x,y])
#print([len(cl) for cl in clustersB])

from math import dist

def nav(cl):
    m = []
    for p in cl:
        k = len([p1 for p1 in cl if dist(p,p1)<=1])
        m.append([k,p[0],p])
    return max(m)[2]
        

da = [nav(cl) for cl in clustersA]
db = [nav(cl) for cl in clustersB]

print(int(sum(x for x,y in da)/len(da)*100_000), int(sum(y for x,y in da)/len(da)*100_000))
print(int(sum(x for x,y in db)/len(db)*100_000), int(sum(y for x,y in db)/len(db)*100_000))

Номер