Учёный-астроном решил провести кластеризацию множества звёзд по их расположению на карте галактики. Кластер – это набор звёзд (точек) на графике, лежащий внутри круга с радиусом 
. Каждая звезда обязательно принадлежит только одному из кластеров.
Помимо обычных кластеров, астроном также обнаружил скопления звёзд, построение которых соответствует ветвям некой параболы, или нескольких парабол. Было принято решение, что рассматриваться будут только те кластеры, которые полностью лежат в тех координатных четвертях, в которых есть хотя бы одна ветвь параболы. Если кластер лежит в нескольких четвертях, то для включения его в рассматриваемую выборку во всех этих четвертях должны быть ветви парабол.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.
Под расстоянием понимается расстояние Евклида между двумя точками 
и 
на плоскости, которое вычисляется по формуле:
В файле А хранятся данные о звёздах трёх кластеров, где 
для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата 
, затем координата 
. Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о шести звёздах, где 
для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звёздах в файле Б аналогична файлу А.
Для каждого файла определите координаты центроида каждого кластера, затем вычислите два числа: 
– среднее арифметическое абсцисс центроидов кластеров, и 
– среднее арифметическое ординат центроидов кластеров.
В ответе запишите четыре числа через пробел: сначала целую часть произведений 
и 
для файла А, далее целую часть произведения 
и 
для файла Б.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в 
, перейдем в раздел «Вставка 
Диаграммы 
Точечная».
Диаграмма для файла А имеет вид:
Разделить все кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:
Код программы для файла А:
from math import *
f = open(’2A.txt’)
s = f.readline()
a = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# Вначале находим по одной точке в файле, принадлежащей каждому кластеру - это будет начальная точка для кластера
# Отобрать их можно либо анализом первых точек в Excel файле, либо программным способом
# Также нужно учесть, что кластер может принадлежать синусоиде
cl = [[[a[0][0], a[0][1]]], [[a[1][0], a[1][1]]]]
for k in range(2):
for j in cl[k]:
for i in range(len(a)):
if a[i] != ’*’:
p = [a[i][0], a[i][1]]
if dist(p, j) < 0.5:
cl[k].append(p)
a[i] = ’*’
sum_x = sum_y = 0 # Переменные для суммы абсцисс и ординат центров
for i in cl:
tx = ty = 0 # Координаты текущего центра кластера
mn = 100000050000 # Минимальное расстояние
for j in i:
x1, y1 = j
sm = 0 # Суммарное расстояние
for k in i:
x2, y2 = k
sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
if sm < mn:
mn = sm
tx, ty = x1, y1
sum_x += tx
sum_y += ty
print(int(sum_x / 2 * 100))
print(int(sum_y / 2 * 100))
Диаграмма для файла Б имеет вид:
Разделить все кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:
Код программы для файла Б:
from math import *
f = open(’2B.txt’)
s = f.readline()
a = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# Вначале находим по одной точке в файле, принадлежащей каждому кластеру - это будет начальная точка для кластера
# Отобрать их можно либо анализом первых точек в Excel файле, либо программным способом
# Также нужно учесть, что кластер может принадлежать синусоиде
cl = [[[a[10][0], a[10][1]]], [[a[7][0], a[7][1]]], [[a[4][0], a[4][1]]], [[a[0][0], a[0][1]]]]
a.pop(10), a.pop(7), a.pop(4), a.pop(0)
for k in range(4):
for j in cl[k]:
for i in range(len(a)):
if a[i] != ’*’:
p = [a[i][0], a[i][1]]
if dist(p, j) < 0.5:
cl[k].append(p)
a[i] = ’*’
sum_x = sum_y = 0 # Переменные для суммы абсцисс и ординат центров
for i in cl:
tx = ty = 0 # Координаты текущего центра кластера
mn = 100000050000 # Минимальное расстояние
for j in i:
x1, y1 = j
sm = 0 # Суммарное расстояние
for k in i:
x2, y2 = k
sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
if sm < mn:
mn = sm
tx, ty = x1, y1
sum_x += tx
sum_y += ty
print(int(sum_x / 4 * 1000))
print(int(sum_y / 4 * 1000))