27.06 Поиск двойных/тройных звездных систем

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

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

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

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

Код программы

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.txt")
s = f.readline()
a = [list(map(float, i.replace(",", ".").split())) for i in f]
cl = dbscan(a, 0.45)
cl_total = []
for i in cl:
    if len(i) > 10: cl_total.append(i)

t = 0.02 # Для файла А
t = 0.01 # Для файла Б
ans = []
for i in cl_total: # Проходим по каждому элементу в списке cl_total
    found_star = dbscan(i, t) # Применяем алгоритм DBSCAN
    tr_stars = [] # Список для тройных звездных систем
    mn_starsys = [] # Список для хранения звездной системы с максимальным расстоянием
    # Проходим по каждому кластеру, найденному алгоритмом DBSCAN
    for j in found_star:
        if len(j) == 3: # Проверяем, состоит ли кластер из трех звезд
            # Проверяем является ли остроугольным треугольником
            d1 = dist(j[0], j[1])
            d2 = dist(j[0], j[2])
            d3 = dist(j[1], j[2])
            if (d1 <= t) and (d2 <= t) and (d3 <= t):
                tr_stars.append(j)
    mn_per = 100000000000 # Переменная для хранения максимального длины стороны
    for j in tr_stars: # Проходим по всем найденным тройным системам
                                                                                                  
                                                                                                  
        # Вычисляем периметр
        d1 = dist(j[0], j[1])
        d2 = dist(j[0], j[2])
        d3 = dist(j[1], j[2])
        if d1 + d2 + d3 < mn_per:
            mn_per = d1 + d2 + d3 # Обновляем максимальное расстояние
            mn_starsys = j # Сохраняем текущую звездную систему как систему с максимальным расстоянием
    ans.append(mn_starsys)

# Рассчитываем среднее значение
res_X = 0
res_Y = 0
for i in ans:
    res_X += (i[0][0] + i[1][0] + i[2][0])
    res_Y += (i[0][1] + i[1][1] + i[2][1])

print(int(abs(res_X / 9) * 10000))  # Для файла А
print(int(abs(res_Y / 9) * 10000))  # Для файла А

print(int(abs(res_X / 12) * 10000))  # Для файла Б
print(int(abs(res_Y / 12) * 10000))  # Для файла Б