Безумный учёный, одержимый идеей контроля над галактикой, решил исследовать звёзды в трёхмерном пространстве своего секретного лабораторного комплекса. Он провёл кластеризацию звёзд по их расположению. Кластер звёзд — это набор точек, каждая из которых находится от хотя бы одной другой звезды на расстоянии не более 
условных единиц. Каждая звезда принадлежит только одному кластеру.
Истинный центр кластера, или центроид, — это звезда, сумма расстояний от которой до всех остальных звёзд кластера минимальна.
Расстояние между двумя точками 
и 
вычисляется по формуле:
Аномалиями называются точки, удалённые более чем на одну условную единицу от всех точек кластеров. Аномалии в расчётах не учитываются.
В файле A хранятся данные о звёздах четырёх кластеров, где 
для каждого кластера. В каждой строке указаны координаты звезды: 
, 
, 
. Значения — вещественные числа в условных единицах. Количество звёзд не превышает 1100.
В файле B хранятся данные о звёздах трёх кластеров, где 
для каждого кластера. Количество звёзд не превышает 25000. Структура данных аналогична файлу A.
Для каждого файла найдите координаты центроида каждого кластера, затем вычислите 
— квадрат произведения средних арифметических абсцисс, ординат и аппликат центроидов.
В ответе укажите два числа через пробел: сначала целую часть 
для файла A, затем целую часть 
для файла B.
Внимание! График приведён для иллюстрации и не связан с заданием. Используйте данные из прилагаемого файла.
Оценим расположение кластеров, открыв файлы в 
и построив точечные диаграммы через раздел «Вставка 
Диаграммы 
Точечная». Это даст представление о двухмерной проекции на плоскость 
.
Диаграмма для файла A имеет вид:
Диаграмма для файла B имеет вид:
Применяем алгоритм DBSCAN для кластеризации с заданными радиусами. Для каждого кластера находим центроид, минимизируя сумму расстояний до других звёзд. Затем вычисляем 
на основе средних координат центроидов.
Код для файла A:
from math import *
def dbscan(a, r):
cl = [] # Инициализируем список для хранения кластеров
while a: # Пока есть элементы в входном массиве ’a’
cl.append([a.pop(0)])
for i in cl[-1]: # Проходим по элементам последнего кластера
for j in a[:]:
if dist(i, j) <= r:
cl[-1].append(j) # Добавляем ’j’ в текущий кластер
a.remove(j) # Удаляем ’j’ из списка ’a’, чтобы не проверять его снова
return cl
f = open("4_A.txt")
a = [list(map(float, i.replace(",", ".").split())) for i in f]
cl = dbscan(a, 1.2) # Для файла А
cl_total = []
for i in cl:
if len(i) > 10: cl_total.append(i)
sum_x = sum_y = sum_z = 0
for cluster in cl_total:
tx = ty = tz = 0
mn = 10 ** 20
for centroid in cluster:
sm = 0
for star in cluster:
sm += dist(centroid, star)
if sm < mn:
mn = sm
tx, ty, tz = centroid[0], centroid[1], centroid[2]
sum_x += tx
sum_y += ty
sum_z += tz
print(int(((sum_x / 4 * sum_y / 4 * sum_z / 4) ** 2) / 8))
Код для файла B:
def dbscan(a, r):
cl = [] # Инициализируем список для хранения кластеров
while a: # Пока есть элементы в входном массиве ’a’
cl.append([a.pop(0)])
for i in cl[-1]: # Проходим по элементам последнего кластера
for j in a[:]:
if dist(i, j) <= r:
cl[-1].append(j) # Добавляем ’j’ в текущий кластер
a.remove(j) # Удаляем ’j’ из списка ’a’, чтобы не проверять его снова
return cl
f = open("4_B.txt")
s = f.readline()
a = [list(map(float, i.replace(",", ".").split())) for i in f]
cl = dbscan(a, 1)
cl_total = []
for i in cl:
if len(i) > 10: cl_total.append(i)
sum_x = sum_y = sum_z = 0
for cluster in cl_total:
tx = ty = tz = 0
mn = 10 ** 20
for centroid in cluster:
sm = 0
for star in cluster:
sm += dist(centroid, star)
if sm < mn:
mn = sm
tx, ty, tz = centroid[0], centroid[1], centroid[2]
sum_x += tx
sum_y += ty
sum_z += tz
print(int(((sum_x / 3 * sum_y / 3 * sum_z / 3) ** 2) * 20))