Задача к ЕГЭ по информатике на тему «Анализ данных (звезды)» №21

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, каждая из которых находится от хотя бы одной другой звезды на расстоянии не более $R$ условных единиц. Каждая звезда обязательно принадлежит только одному из кластеров.

Двойная звездная система – это система, в которой две звезды находятся на расстоянии не более $t$ . При этом других звезд на расстоянии менее $t$ у этих двух звезд быть не должно.

Под расстоянием понимается расстояние Евклида между двумя точками $A(x1,y1)$ и $B(x2,y2)$ на плоскости, которое вычисляется по формуле:

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.

В файле A хранятся данные о звёздах пяти кластеров, где $R = 0.4$ , $t = 0.03$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 10000.

В файле Б хранятся данные о звёздах четырех кластеров, где $R = 0.65$ , $t = 0.009$ для каждого кластера. Известно, что количество звёзд не превышает 20 000. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла в каждом кластере найдите двойную звездную систему с максимальным расстоянием между звездами. Затем вычислите два числа: $Px$ — среднее арифметическое абсцисс звезд, и $Py$ – среднее арифметическое ординат звезд.

В ответе запишите четыре числа через пробел: сначала целую часть произведения $P ⋅1000 x$ для файла А, затем $Py ⋅1000$ для файла А, далее целую часть произведения $Px ⋅1000$ для файла Б и $Py ⋅1000$ для файла Б.

Возможные данные одного из файлов иллюстрированы графиком.

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

Диаграмма для файла Б имеет вид:

Для разделения звезд на кластеры будем использоваться функцию dbscan. Дальше основная идея решения будет заключаться в том, что мы будем проходить по каждой точке в найденных кластерах и с помощью того же метода dbscan для каждого кластера найти списки звезд, расстояние между которыми менее 0.03 в А файле (менее 0.009 в Б файле). Далее в каждом кластере нужно оставить только те списки, в которых количество звезд равно двум – то есть только двойные звездные системы. В конце остается дело за малым: для каждой звездной системы в каждом кластере найти максимальное расстояние между звездами, а затем расчитать среднее арифметическое их координат между всеми найденными парами звёзд.

Код программы для А файла

from math import *
def dbscan(a, r):
    cl = [] # Инициализируем список для хранения кластеров
    while a: # Пока есть элементы в входном массиве ’a’
    # Создаем новый кластер и добавляем в него первый элемент из ’a’
        cl.append([a.pop(0)])
        for i in cl[-1]: # Проходим по элементам последнего кластера
        # Проверяем  каждый элемент ’j’ в оставшихся элементах ’a’
            for j in a[:]:
            # Если расстояние между ’i’ и ’j’ меньше радиуса ’r’
                if dist(i, j) < r:
                    cl[-1].append(j) # Добавляем ’j’ в текущий кластер
                    a.remove(j) # Удаляем ’j’ из списка ’a’, чтобы не проверять его снова
    return cl

f = open("2_A.txt")
s = f.readline()
a = [list(map(float, i.replace(",", ".").split())) for i in f]
cl = dbscan(a, 0.4)
cl_total = []
c = 0
for i in cl:
    if len(i) > 10:
        cl_total.append(i)
res = []
t = 0.03  # Устанавливаем радиус для алгоритма DBSCAN
for i in cl_total: # Проходим по каждому элементу в списке cl_total
    found_star = dbscan(i, t) # Применяем алгоритм DBSCAN
    bin_stars = []  # Список для бинарных звездных систем
    max_star_sys = []
    # Проходим по каждому кластеру, найденному алгоритмом DBSCAN
    for j in found_star:
        if len(j) == 2: # Проверяем, состоит ли кластер из двух звезд
            bin_stars.append(j)  # Добавляем бинарную систему в список
    mx_dist = 0  # Переменная для хранения максимального расстояния
    # Список для хранения звездной системы с максимальным расстоянием
    for j in bin_stars: # Проходим по всем найденным бинарным системам
    # Вычисляем расстояние между звездами в бинарной системе
        if dist(j[0], j[1]) > mx_dist:
            mx_dist = dist(j[0], j[1])  # Обновляем максимальное расстояние
            max_star_sys = j
    # Сохраняем текущую звездную систему как систему с максимальным расстоянием






































































































































































































    res.append(max_star_sys)

res_X = 0
res_Y = 0
for i in res:
    res_X += (i[0][0] + i[1][0])
    res_Y += (i[0][1] + i[1][1])

print(int(res_X / 10 * 1000))
print(int(res_Y / 10 * 1000))

Код программы для Б файла

from math import *

def dbscan(a, r):
    cl = [] # Инициализируем список для хранения кластеров
    while a: # Пока есть элементы в входном массиве ’a’
        # Создаем новый кластер и добавляем в него первый элемент из ’a’
        cl.append([a.pop(0)])
        for i in cl[-1]: # Проходим по элементам последнего кластера
            # Проверяем  каждый элемент ’j’ в оставшихся элементах ’a’
            for j in a[:]:
                # Если расстояние между ’i’ и ’j’ меньше радиуса ’r’
                x = [i[0], i[1]]
                y = [j[0], j[1]]
                if dist(x, y) < r:
                    cl[-1].append(j) # Добавляем ’j’ в текущий кластер
                    a.remove(j) # Удаляем ’j’ из списка ’a’, чтобы не проверять его снова
    return cl

f = open("2_B.txt")
s = f.readline()
a = [list(map(float, i.replace(",", ".").split())) for i in f]
cl = dbscan(a, 0.65)
cl_total = []

for i in cl:
    if len(i) > 20:
        cl_total.append(i)
ans = []
t = 0.009
for cluster in cl_total:
    clust = dbscan(cluster,t)
    duo_stars = []
    max_star_sys = []
    for star_sys in clust:
        if len(star_sys) == 2:
            duo_stars.append(star_sys)
    max_dist = 0
    for i in duo_stars:
        if dist(i[0],i[1]) > max_dist:
            max_dist = dist(i[0],i[1])
            max_star_sys = i
    ans.append(max_star_sys)






































































































































































































sum_X = 0
sum_Y = 0
for i in ans:
    sum_X += i[0][0] + i[1][0]
    sum_Y += i[0][1] + i[1][1]
print(int(sum_X/8*1000))
print(int(sum_Y/8*1000))

Ответ: -22172 12740 -30488 29200