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

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

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

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

d(A, B) = ∘ (x-−-x-)2 +-(y-−-y-)2 2 1 2 1

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

В файле A хранятся данные о звёздах двух кластеров, где $R = 0.5$ , $t = 0.15$ для каждого кластера. В каждой строке записаны координаты одной звезды и её масса (в солнечных массах): $x$ , $y$ , $m$ . Если масса положительная ( $m > 0 » class=»math» src=»/images/inform/quest/quest-7498-12.svg» width=»auto»>), это обычная звезда, если отрицательная (<img decoding=$ ), это нейтронная звезда или чёрная дыра. Значения — вещественные числа в условных единицах. Количество звёзд не превышает 1500.

В файле B хранятся данные о звёздах трёх кластеров, где $R = 0.7$ , $t = 0.025$ для каждого кластера. Количество звёзд не превышает 5500. Структура данных аналогична файлу A.

Для каждого файла в каждом кластере найдите двойную систему из двух нейтронных звёзд ( $− 2.5 < m < 0$ ) с максимальной суммой масс по модулю. Затем вычислите два числа: $Px$ — среднее арифметическое абсцисс найденных звёзд, и $Py$ — среднее арифметическое их ординат.

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

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

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

Диаграмма для файла A:

Диаграмма для файла B:

Для кластеризации используем алгоритм DBSCAN с радиусом $R$ . Затем в каждом кластере применим DBSCAN с радиусом $t$ для поиска двойных систем. Оставим только пары из двух нейтронных звёзд ( $− 2.5 < m < 0$ ) и выберем ту, где сумма масс по модулю минимальна. Вычислим средние $Px$ и $Py$ для всех найденных пар.

Код для файла A:

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("1_A.txt")
a = [list(map(float, i.replace(",", ".").split())) for i in f]
cl = dbscan(a, 0.5)
cl_total = []
for i in cl:
    if len(i) > 10: cl_total.append(i)
t = 0.15
ans = []
for i in cl_total:
    found_star = dbscan(i, t)
    duo_stars = []
    mx_starsys = []
    for j in found_star:
        if len(j) == 2:
            if -2.5 < j[0][2] < 0 and -2.5 < j[1][2] < 0:
                duo_stars.append(j)
    mx_mass = 0
    for j in duo_stars:
        if abs(j[0][2] + j[1][2]) > mx_mass:
            mx_mass = abs(j[0][2] + j[1][2])
            mx_starsys = j
    ans.append(mx_starsys)
# Рассчитываем среднее значение
res_X = 0






































































































































































































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

print(int(res_X / 4 * 200))
print(int(res_Y / 4 * 200))

Код для файла B:

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("1_B.txt")
s = f.readline()
a = [list(map(float, i.replace(",", ".").split())) for i in f]
cl = dbscan(a, 0.7)
cl_total = []
for i in cl:
    if len(i) > 10: cl_total.append(i)
t = 0.025
ans = []
for i in cl_total:
    found_star = dbscan(i, t)
    duo_stars = []
    mx_starsys = []
    for j in found_star:
        if len(j) == 2:
            if -2.5 < j[0][2] < 0 and -2.5 < j[1][2] < 0:
                duo_stars.append(j)
    mx_mass = 0
    for j in duo_stars:
        if abs(j[0][2] + j[1][2]) > mx_mass:
            mx_mass = abs(j[0][2] + j[1][2])
            mx_starsys = j
    ans.append(mx_starsys)
# Рассчитываем среднее значение






































































































































































































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

print(int(res_X / 6 * 200))
print(int(res_Y / 6 * 200))

Ответ: -1088 -1308 -410 -1896