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