27.03 Кластеры нестандартной формы - Каталог заданий по ЕГЭ

Ошибка.
Попробуйте повторить позже

Задача 1#99575Максимум баллов за задание: 2

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

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Центроид не вычисляется для колец, он вычисляется только для кластеров, представляющих собой круг.

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

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

В файле A хранятся данные о звёздах двух кластеров, где $R = 1,5$ для внутреннего кластера и $R = 3,1$ для внешнего кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 1245.

В файле Б хранятся данные о звёздах трёх кластеров, где $R = 4,1$ для двух внутренних кластеров и $R = 17,1$ для внешнего кластера. Известно, что количество звёзд не превышает 9414. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведения $Px ⋅100$ для файла А и $Py ⋅100$ для файла А, далее целую часть произведения $Px ⋅100$ для файла Б и $Py ⋅100$ для файла Б.

Возможные данные одного из файлов иллюстрированы графиком.

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

$PIC$

Вложения к задаче

Показать ответ и решение

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

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

$PIC$

Внутренний кластер симметричен относительно оси Ox и Oy. Радиус внутреннего кластера равен 1.5, соответственно, та или иная звезда будет принадлежать данному кластеру если она удовлетворяет следующему неравенству окружности: $2 2 x + y ≤ 2.25$

Код программы для файла А:

f = open(’27_1_A.txt’)
n = f.readline()
cluster = []  # Создаём список для кластера
for i in range(1245):  # Считываем звёзды из файла
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    if star[0] ** 2 + star[1] ** 2 <= 1.5**2:  # Звезда относится к внутреннему кластеру
        cluster.append(star)

tx = ty = 0
mn = 100000050000

for j in cluster:  # Перебор предполагаемого центроида
    x1, y1 = j
    sm = 0  # Суммарное расстояние
    for k in cluster:  # Перебор всех звёзд для вычисления суммарного расстояния
        x2, y2 = k
        sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
    if sm < mn: # У текущей звезды расстояние до остальных звёзд меньше предыдущей
        mn = sm
        tx, ty = x1, y1 # Сохранение нового центроида

print(int(tx * 100))
print(int(ty * 100))

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

$PIC$

Определим подходящие уравнения окружностей, внутри которых лежат внутренние кластеры. Геометрические центры левого и правого кластеров находятся около точки (-7; 0) и (7; 0) соответственно, и для них можно выбрать радиус 4.5, не задевая внешний кластер. Получим следующие неравенства для внутренних кластеров:

$2 2 2 (x− 7) + y ≤ 4.5$ – для левого кластера

$(x+ 7)2 + y2 ≤ 4.52$ – для правого кластера

Код программы для файла Б:

f = open(’27_1_B.txt’)
n = f.readline()
clusters = [[] for i in range(2)]
for i in range(9414):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    if (star[0] - 7) ** 2 + star[1] ** 2 <= 4.5 ** 2:
        clusters[0].append(star)
    elif (star[0] + 7) ** 2 + star[1] ** 2 <= 4.5 ** 2:
        clusters[1].append(star)

sum_x = sum_y = 0
for i in clusters:
    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 / len(clusters) * 100))
print(int(sum_y / len(clusters) * 100))

Ответ: -8 -9 -5 -4

Ошибка.
Попробуйте повторить позже

Задача 2#99578Максимум баллов за задание: 2

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

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Центроид не вычисляется для колец, он вычисляется только для кластеров, представляющих собой круг.

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

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

В файле A хранятся данные о звёздах трёх кластеров, где $R = 3$ для нижнего кластера и для верхнего внешнего кластера и $R = 2$ для верхнего внутреннего кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 966.

В файле Б хранятся данные о звёздах четырёх кластеров, $R = 3$ для нижнего правого кластера и для верхнего внешнего кластера и $R = 2$ для верхнего внутреннего кластера и $R = 4$ для нижнего левого кластера. Известно, что количество звёзд не превышает 4798. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведения $P ⋅333 x$ для файла А и $Py ⋅666$ для файла А, далее целую часть произведения $Px ⋅321$ для файла Б и $Py ⋅123$ для файла Б.

Возможные данные одного из файлов иллюстрированы графиком.

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

$PIC$

Вложения к задаче

Показать ответ и решение

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

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

$PIC$

Рассмотрим подробно нижний кластер. Он симметричен относительно оси Oy и Ox. Его радиус равен $3$ . Следовательно, если координаты точки удовлетворяют неравенству окружности: $x2 + y2 ≤ 9$ , значит, это точка принадлежит нижнему кластеру.

Изучим верхний внутренний кластер, его радиус равен $2$ . Центр круга находится в точке (-5;4). Следовательно, если координаты точки удовлетворяют неравенству окружности: $(x +5)2 + (y− 4)2 ≤ 4$ , значит, это точка принадлежит верхнему внутреннему кластеру.

Если точка не удовлетворяет ни одному из выше описанных неравенств, значит, она находится во внешнем кластере (кольце). Поскольку мы не высчитываем центроид колец, то данные точки нас не интересуют.

Код программы для файла А:

f = open(’27_4_A.txt’)
n = f.readline()
clusters = [[] for i in range(2)]
for i in range(966):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    x,y = star[0],star[1]
    if x**2 + y ** 2 <= 9:
        clusters[0].append(star)
    elif (x + 5)**2 + (y - 4) ** 2 <= 4:
        clusters[1].append(star)
sum_x = sum_y = tx = ty = 0
for i in clusters:
    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 / len(clusters) * 333))
print(int(sum_y / len(clusters) * 666))

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

$PIC$

Разберем подробнее нижний правый кластер. Центр круга находится в точке (1;-1). Его радиус равен $3$ . Следовательно, если координаты точки удовлетворяют неравенству окружности: $(x− 1)2 + (y+ 1)2 ≤ 9$ , значит, это точка принадлежит нижнему правому кластеру.

Изучим поподробнее нижний левый кластер. Центр круга находится в точке (-5;-5). Его радиус равен $4$ . Следовательно, если координаты точки удовлетворяют неравенству окружности: $(x+ 5)2 + (y+ 5)2 ≤ 16$ , значит, это точка принадлежит нижнему левому кластеру.

Рассмотрим верхний внутренний кластер. Центр круга находится в точке (-6;3). Его радиус равен $2$ . Следовательно, если координаты точки удовлетворяют неравенству окружности: $(x+ 6)2 + (y− 3)2 ≤ 4$ , значит, это точка принадлежит верхнему внутреннему кластеру.

Если точка не удовлетворяет ни одному из выше описанных неравенств, значит, она находится во внешнем кластере (кольце). Поскольку мы не высчитываем центроид колец, то данные точки нас не интересуют.

Код программы для файла Б:

f = open(’27_4_B.txt’)
n = f.readline()
clusters = [[] for i in range(3)]
for i in range(4798):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    x,y = star[0],star[1]
    if ((x - 1) ** 2 + (y  + 1) ** 2) <= 9:
        clusters[0].append(star)
    elif ((x - (-6)) ** 2 + (y - 3) ** 2) <= 4:
        clusters[1].append(star)
    elif ((x + 5)**2 + (y + 5)**2) <= 16:
        clusters[2].append(star)
sum_x = sum_y = tx = ty = 0
for i in clusters:
    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 / len(clusters) * 321))
print(int(sum_y / len(clusters) * 123))

Ответ: -800 1274 -1081 -120

Ошибка.
Попробуйте повторить позже

Задача 3#99579Максимум баллов за задание: 2

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

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Центроид не вычисляется для колец, он вычисляется только для кластеров, представляющих собой круг.

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

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

В файле A хранятся данные о звёздах двух кластеров, где $R = 2.1$ у внутреннего кластера и $R = 5.1$ у внешнего кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 1029.

В файле Б хранятся данные о звёздах четырёх кластеров, где $R = 2.1$ у внутренних кластеров, $R = 5.1$ у внешних кластеров. Известно, что количество звёзд не превышает 8166. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведения $Px ⋅525$ для файла А и $Py ⋅525$ для файла А, далее целую часть произведения $Px ⋅300$ для файла Б и $Py ⋅300$ для файла Б.

Возможные данные одного из файлов иллюстрированы графиком.

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

$PIC$

Вложения к задаче

Показать ответ и решение

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

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

$PIC$

Определим уравнение окружности, внутри которой лежит внутренний кластер. Геометрический центр внутреннего кластера находится приблизительно в точке (0;3.5). Значит, если координаты точки удовлетворяют неравенству окружности: $2 2 2 x + (y− 3.5) ≤ 2.1$ , тогда эта звезда относится ко внутреннему кластеру.

Код программы для файла А:

f = open(’27_5_A.txt’)
n = f.readline()
cluster = []
for i in range(1029):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    x, y = star[0], star[1]
    if x ** 2 + (y - 3.5) ** 2 <= 2.1 ** 2:
        cluster.append(star)

sum_x = sum_y = tx = ty = 0
mn = 100000050000
for j in cluster:
    x1, y1 = j
    sm = 0
    for k in cluster:
        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 * 525))
print(int(sum_y * 525))

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

$PIC$

Нанесём на график прямую: $y = 9.5− x$ :

$PIC$

Теперь можем провести определить какие звезды к каким кластерам относятся.

Сначала разделим на группы по два кластера.

Точки, которые удовлетворяют неравенству: $y ≥ 9.5 − x$ находятся в верхней (первой) группе.

Точки, которые удовлетворяют неравенству: $y ≤ 9.5 − x$ находятся в нижней (второй) группе.

Рассмотрим подробно первую группу:

Радиус внутренний кластер равен $2$ , геометрический центр кластера находится в точке (8;7). Следовательно, если координаты точки удовлетворяют неравенству окружности: $2 2 2 (x − 8) + (y − 7) ≤ 2.1$ , тогда эта звезда относится ко внутреннему кластеру первой группы.

Рассмотрим подробно вторую группу:

Радиус внутренний кластер равен $2.1$ , геометрический центр кластера находится в точке (2;2). Следовательно, если координаты точки удовлетворяют неравенству окружности: $(x − 2)2 + (y − 2)2 ≤ 2.12$ , тогда эта звезда относится ко внутреннему кластеру второй группы.

Код программы для файла Б:

f = open(’27_3_B.txt’)
n = f.readline()
clusters = [[] for i in range(2)]
for i in range(8166):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    x, y = star[0], star[1]
    if y >= 9.5 - x:
        if (x - 8) ** 2 + (y - 7) ** 2 < 2.1 ** 2:
            clusters[0].append(star)
    else:
        if (x - 2) ** 2 + (y - 2) ** 2 < 2.1 ** 2:
            clusters[1].append(star)

sum_x = sum_y = 0
for i in clusters:
    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 / len(clusters) * 300))
print(int(sum_y / len(clusters) * 300))

Ответ: -47 1819 1474 1331

Ошибка.
Попробуйте повторить позже

Задача 4#103834Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, каждая из которых находится от хотя бы одной другой звезды на расстоянии не более R условных единиц. Каждая звезда обязательно принадлежит только одному из кластеров. Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x1,y1)$ и $B (x2,y2)$ на плоскости, которое вычисляется по формуле:

$∘ --------2---------2- d(A,B ) = (x2 − x1) + (y2 − y1)$

В файле A хранятся данные о звёздах двух кластеров, где $R = 0,2$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 2000.

В файле Б хранятся данные о звёздах четырех кластеров, где $R = 0,2$ для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.

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

Возможные данные одного из файлов иллюстрированы графиком.

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

Вложения к задаче

Показать ответ и решение

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

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

$PIC$

Из нее видно, что кластеры имеют необычную форму, поэтому для разделения точек по кластерам будем использовать метод dbscan. Чтобы найти стартовые точки определим области, в которых кластеры не перессекаются. Для верхнего кластера будем использовать координаты: $x ∈ [− 1;− 0.5],y ∈ [0;0.2]$ . Для нижнего будем использовать координаты: $x ∈ [0;0.5],y ∈ [− 0.2;0]$ .

Код программы для файла А:

from math import *
f = open(’3_A.txt’)
s = f.readline() # Считываем первую строку файла с названиями столбцов
# сохраняем массив данных
st = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# подбираем по 1 звезде для каждого кластера меняя параметры
# for i in range(len(st)):
#     if 0 < st[i][0] < 0.5 and -0.2 < st[i][1] < 0:
#         print(i)
#         break

a = [[[st[47][0], st[47][1]]], [[st[17][0], st[17][1]]]]

st.pop(47), st.pop(17)

# разделяем звезды на кластеры методом dbscan
for k in range(2):
    for j in a[k]:
        for i in range(len(st)):
            if st[i] != ’*’:
                p = [st[i][0], st[i][1]]
                if dist(p, j) < 0.2:
                    a[k].append(p)
                    st[i] = ’*’

sum_x = sum_y = 0  # Переменные для суммы абсцисс и ординат периферий
for i in a:
    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 * 10000))
print(int(sum_y / 2 * 10000))

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

$PIC$

Из нее видно, что кластеры имеют необычную форму, поэтому для разделения точек по кластерам будем использовать метод dbscan. Чтобы найти стартовые точки определим области, в которых кластеры не перессекаются. Для самого нижнего кластера будем использовать координаты: $x ∈ [− 5;5],y ∈ [− 6;− 2]$ . Для самого левого кластера будем использовать координаты: $x ∈ [− 10;− 5],y ∈ [0;2]$ . Для самого верхнего будем использовать координаты: $x ∈ [0;5],y ∈ [6;8]$ . Для самого правого будем использовать координаты: $x ∈ [10;15],y ∈ [0;6]$ .

Код программы для файла Б:

from math import *
f = open(’3_B.txt’)
s = f.readline() # Считываем первую строку файла с названиями столбцов
# сохраняем массив данных
st = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# подбираем по 1 звезде для каждого кластера меняя параметры
# for i in range(len(st)):
#     if 10 < st[i][0] < 15 and 0 < st[i][1] < 6:
#         print(i)
#         break

a = [[[st[11][0], st[11][1]]], [[st[19][0], st[19][1]]], [[st[17][0], st[17][1]]], [[st[2][0], st[2][1]]]]

st.pop(11), st.pop(19), st.pop(17), st.pop(2)

# разделяем звезды на кластеры методом dbscan
for k in range(4):
    for j in a[k]:
        for i in range(len(st)):
            if st[i] != ’*’:
                p = [st[i][0], st[i][1]]
                if dist(p, j) < 0.2:
                    a[k].append(p)
                    st[i] = ’*’

sum_x = sum_y = 0  # Переменные для суммы абсцисс и ординат периферий
for i in a:
    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 * 10000))
print(int(sum_y / 4 * 10000))

Ответ: 5322 2579 18208 16188

Ошибка.
Попробуйте повторить позже

Задача 5#104849Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, образующий цветы на небесном полотне. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинная периферия кластера, или перифероид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера максимальна.

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

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

В файле A хранятся данные о звёздах трёх цветков. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 10000.

В файле Б хранятся данные о звёздах пяти цветков. Известно, что количество звёзд не превышает 25000. Структура хранения информации о звёздах в файле Б аналогична файлу А.

Для каждого файла определите координаты периферии каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс периферий кластеров, и $Py$ – среднее арифметическое ординат периферий кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведений $Px ⋅100$ и $Py ⋅100$ для файла А, далее целую часть произведения $Px ⋅100$ и $Py ⋅100$ для файла Б.

Возможные данные одного из файлов иллюстрированы графиком.

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

$PIC$

Вложения к задаче

Показать ответ и решение

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

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

$PIC$

Просто разделить кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:

Код программы для файла А:

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_total = dbscan(a, 0.2)

sum_x = sum_y = 0  # Переменные для суммы абсцисс и ординат центров
for i in cl_total:
    tx = ty = 0  # Координаты текущего центра кластера
    mn = 0  # Минимальное расстояние
    for j in i:  # Перебор предполагаемого центроида
        sm = 0  # Суммарное расстояние
        for k in i:  # Перебор остальных звёзд для вычисления расстояний
            sm += dist(k, j)
        if sm > mn:
            mn = sm
            tx, ty = j
    sum_x += tx
    sum_y += ty

print(int(sum_x / 3 * 100))
print(int(sum_y / 3 * 100))

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

$PIC$

Просто разделить кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:

Код программы для файла Б:

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_total = dbscan(a, 0.2)

sum_x = sum_y = 0  # Переменные для суммы абсцисс и ординат центров
for i in cl_total:
    tx = ty = 0  # Координаты текущего центра кластера
    mn = 0  # Минимальное расстояние
    for j in i:  # Перебор предполагаемого центроида
        sm = 0  # Суммарное расстояние
        for k in i:  # Перебор остальных звёзд для вычисления расстояний
            sm += dist(k, j)
        if sm > mn:
            mn = sm
            tx, ty = j
    sum_x += tx
    sum_y += ty

print(int(sum_x / 5 * 100))
print(int(sum_y / 5 * 100))

Ответ: 147 313 1179 946

Ошибка.
Попробуйте повторить позже

Задача 6#104850Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий по контуру пятиконечной звезды. Каждая звезда обязательно принадлежит только одному из кластеров.

Помимо звёзд на звездном небе существует Млечный Путь, который не является кластером и не учитывается при кластеризации.

Истинный центр кластера, или центроид, – это одна из звёзд кластера, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

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

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

В файле A хранятся данные о звёздах трёх кластеров. В каждой строке файла записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 2500.

В файле Б хранятся данные о звёздах шести кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведения $|Px|⋅1000$ для файла А и $|Py|⋅1000$ для файла А, далее целую часть деления $|Px|⋅1000$ для файла Б и $|Py |⋅1000$ для файла Б.

Возможные данные одного из файлов иллюстрированы графиком.

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

$PIC$

Вложения к задаче

Показать ответ и решение

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

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

$PIC$

Просто разделить кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:

Код программы для файла А:

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.2)
cl_total = []
c = 0
for i in cl:
    if len(i) > 10 and (max([j[0] for j in i]) - min([j[0] for j in i])) < 4:
        cl_total.append(i)



sum_x = sum_y = 0  # Переменные для суммы абсцисс и ординат центров
for i in cl_total:
    tx = ty = 0  # Координаты текущего центра кластера
    mn = 100000050000  # Минимальное расстояние
    for j in i:  # Перебор предполагаемого центроида
        sm = 0  # Суммарное расстояние
        for k in i:  # Перебор остальных звёзд для вычисления расстояний
            sm += dist(k, j)
        if sm < mn:
            mn = sm
            tx, ty = j
    sum_x += tx
    sum_y += ty

print(int(abs(sum_x / 3) * 1000))
                                                                                                  
                                                                                                  
print(int(abs(sum_y / 3) * 1000))

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

$PIC$

Просто разделить кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:

Код программы для файла Б:

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.2)
cl_total = []
c = 0
for i in cl:
    if len(i) > 10 and (max([j[0] for j in i]) - min([j[0] for j in i])) < 15:
        cl_total.append(i)



sum_x = sum_y = 0  # Переменные для суммы абсцисс и ординат центров
for i in cl_total:
    tx = ty = 0  # Координаты текущего центра кластера
    mn = 100000050000  # Минимальное расстояние
    for j in i:  # Перебор предполагаемого центроида
        sm = 0  # Суммарное расстояние
        for k in i:  # Перебор остальных звёзд для вычисления расстояний
            sm += dist(k, j)
        if sm < mn:
            mn = sm
            tx, ty = j
    sum_x += tx
    sum_y += ty

print(int(abs(sum_x / 6) * 1000))
                                                                                                  
                                                                                                  
print(int(abs(sum_y / 6) * 1000))

Ответ: 1042 1688 280 200

Ошибка.
Попробуйте повторить позже

Задача 7#104930Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, образующий звезду на небесном полотне. Каждая звезда обязательно принадлежит только одному из кластеров.

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

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

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

∘ -------------------- d(A,B ) = (x2 − x1)2 + (y2 − y1)2

В файле A хранятся данные о звёздах четырёх кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 5500.

В файле Б хранятся данные о звёздах восьми кластеров. Известно, что количество звёзд не превышает 35000. Структура хранения информации о звёздах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ – среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров. Кластеры, принадлежащие синусоиде, в вычислениях не учитывать.

В ответе запишите четыре числа через пробел: сначала целую часть произведений $|Px|⋅100$ и $|Py|⋅100$ для файла А, далее целую часть произведения $|Px|⋅1000$ и $|Py|⋅1000$ для файла Б.

Возможные данные одного из файлов иллюстрированы графиком.

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

Вложения к задаче

Показать ответ и решение

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

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

$PIC$

Просто разделить кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:

Код программы для файла А:

from math import *

f = open(’1A.txt’)
s = f.readline()
a = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# Вначале находим по одной точке в файле, принадлежащей каждому кластеру - это будет начальная точка для кластера
# Отобрать их можно либо анализом первых точек в Excel файле, либо программным способом
# Также нужно учесть, что кластер может принадлежать синусоиде
cl = [[[a[0][0], a[0][1]]], [[a[4286][0], a[4286][1]]]]
a.pop(4286), a.pop(0)
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.4:
                    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))

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

$PIC$

Просто разделить все кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:

Код программы для файла Б:

from math import *

f = open(’1B.txt’)
s = f.readline()
a = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# Вначале находим по одной точке в файле, принадлежащей каждому кластеру - это будет начальная точка для кластера
# Отобрать их можно либо анализом первых точек в Excel файле, либо программным способом
# Также нужно учесть, что кластер может принадлежать синусоиде
cl = [[[a[3779][0], a[3779][1]]], [[a[33773][0], a[33773][1]]], [[a[4][0], a[4][1]]], [[a[0][0], a[0][1]]], [[a[3785][0], a[3785][1]]]]
a.pop(33773), a.pop(3785), a.pop(3779), a.pop(4), a.pop(0)
for k in range(5):
    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.4:
                    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(abs(sum_x / 5) * 1000))
print(int(abs(sum_y / 5) * 1000))

Ответ: 721 12 532 1177

Ошибка.
Попробуйте повторить позже

Задача 8#104931Максимум баллов за задание: 2

Учёный-астроном решил провести кластеризацию множества звёзд по их расположению на карте галактики. Кластер – это набор звёзд (точек) на графике, лежащий внутри круга с радиусом $H$ . Каждая звезда обязательно принадлежит только одному из кластеров.

Помимо обычных кластеров, астроном также обнаружил скопления звёзд, построение которых соответствует ветвям некой параболы, или нескольких парабол. Было принято решение, что рассматриваться будут только те кластеры, которые полностью лежат в тех координатных четвертях, в которых есть хотя бы одна ветвь параболы. Если кластер лежит в нескольких четвертях, то для включения его в рассматриваемую выборку во всех этих четвертях должны быть ветви парабол.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

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

∘ -------------------- d(A,B ) = (x2 − x1)2 + (y2 − y1)2

В файле А хранятся данные о звёздах трёх кластеров, где $H = 3$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 1000.

В файле Б хранятся данные о шести звёздах, где $H = 3$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звёздах в файле Б аналогична файлу А.

Для каждого файла определите координаты центроида каждого кластера, затем вычислите два числа: $Cx$ – среднее арифметическое абсцисс центроидов кластеров, и $C y$ – среднее арифметическое ординат центроидов кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведений $Cx ⋅100$ и $Cy ⋅100$ для файла А, далее целую часть произведения $Cx ⋅1000$ и $Cy ⋅1000$ для файла Б.

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

Вложения к задаче

Показать ответ и решение

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

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

$PIC$

Разделить все кластеры с помощью прямых не получится. Воспользуемся методом 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))

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

$PIC$

Разделить все кластеры с помощью прямых не получится. Воспользуемся методом 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))

Ответ: 46 403 8715 15469

Ошибка.
Попробуйте повторить позже

Задача 9#104932Максимум баллов за задание: 2

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

Центр звёздного скопления – это одна из звёзд, сумма расстояний от которой до всех остальных звёзд в кластере минимальна. Галлей считает, что эта звезда является ключевой для понимания структуры скопления.

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

∘ -------------------- d(A,B ) = (x2 − x1)2 + (y2 − y1)2

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

В файле А хранятся данные о четырех кластерах звёзд, где $R = 0.45$ для каждого кластера. В каждой строке записана информация о расположении одной звезды: сначала координата $x$ , затем координата $y$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 1000.

В файле Б хранятся данные о шести кластерах звёзд, где $R = 0.4$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звёздах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра звёздного скопления каждого кластера, затем вычислите два числа: $Zx$ – среднее арифметическое абсцисс центров звёздных скоплений, и $Zy$ – среднее арифметическое ординат центров звёздных скоплений. Если в каждой четверти лежит одинаковое количество центров звёздных скоплений, считать $Zx$ и $Zy$ равными 0.

В ответе запишите четыре числа через пробел: сначала целую часть произведений $|Zx |⋅100$ и $|Zy|⋅100$ для файла А, далее целую часть произведения $|Zx|⋅1000$ и $|Zy|⋅1000$ для файла Б.

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

Вложения к задаче

Показать ответ и решение

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

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

$PIC$

Разделить все кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:

Код программы для файла А:

from math import *

f = open(’3A.txt’)
s = f.readline()
a = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# Вначале находим по одной точке в файле, принадлежащей каждому кластеру - это будет начальная точка для кластера
# Отобрать их можно либо анализом первых точек в Excel файле, либо программным способом
# Также нужно учесть, что кластер может принадлежать синусоиде
cl = [[[a[0][0], a[0][1]]], [[a[7][0], a[7][1]]], [[a[2][0], a[2][1]]], [[a[9][0], a[9][1]]]]
a.pop(9), a.pop(7), a.pop(2), 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.45:
                    cl[k].append(p)
                    a[i] = ’*’
s_xy = []
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
    s_xy.append([tx, ty, 0])
coords = [0, 0, 0, 0]
for i in s_xy:
    if i[0] > 0 and i[1] > 0:
        coords[0] += 1
        i[2] = 1
    elif i[0] > 0 and i[1] < 0:
                                                                                                     
                                                                                                     
        coords[3] += 1
        i[2] = 4
    elif i[0] < 0 and i[1] > 0:
        coords[1] += 1
        i[2] = 2
    elif i[0] < 0 and i[1] < 0:
        coords[2] += 1
        i[2] = 3
if coords.count(coords[0]) == 4: # Если количество центров кластеров одинаково во всех координатных плоскостях
    print(0, 0) # Ответом будет 0, 0
else: # В противном случае, рассматриваем центры кластеров
    mx = coords.index(max(coords)) + 1  # Координатная четверть, в которой лежит максимальное количество центров кластеров
    s_ost = [i for i in s_xy if i[2] != mx]
    sum_x = sum(i[0] for i in s_ost)
    sum_y = sum(i[1] for i in s_ost)
    print(int(sum_x * 100 / len(s_ost)), int(sum_y * 100 / len(s_ost)))

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

$PIC$

Разделить все кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:

Код программы для файла Б:

from math import *

f = open(’3B.txt’)
s = f.readline()
a = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# Вначале находим по одной точке в файле, принадлежащей каждому кластеру - это будет начальная точка для кластера
# Отобрать их можно либо анализом первых точек в Excel файле, либо программным способом
# Также нужно учесть, что кластер может принадлежать синусоиде
cl = [[[a[40][0], a[40][1]]], [[a[19][0], a[19][1]]], [[a[15][0], a[15][1]]], [[a[16][0], a[16][1]]], [[a[18][0], a[18][1]]], [[a[25][0], a[25][1]]]]
a.pop(40), a.pop(25), a.pop(19), a.pop(18), a.pop(16), a.pop(15)
for k in range(6):
    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.4:
                    cl[k].append(p)
                    a[i] = ’*’
s_xy = []
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
    s_xy.append([tx, ty, 0])
coords = [0, 0, 0, 0]
for i in s_xy:
    if i[0] > 0 and i[1] > 0:
        coords[0] += 1
        i[2] = 1
    elif i[0] > 0 and i[1] < 0:
                                                                                                     
                                                                                                     
        coords[3] += 1
        i[2] = 4
    elif i[0] < 0 and i[1] > 0:
        coords[1] += 1
        i[2] = 2
    elif i[0] < 0 and i[1] < 0:
        coords[2] += 1
        i[2] = 3
if coords.count(coords[0]) == 4: # Если количество центров кластеров одинаково во всех координатных плоскостях
    print(0, 0) # Ответом будет 0, 0
else: # В противном случае, рассматриваем центры кластеров
    mx = coords.index(max(coords)) + 1  # Координатная четверть, в которой лежит максимальное количество центров кластеров
    s_ost = [i for i in s_xy if i[2] != mx]
    sum_x = sum(i[0] for i in s_ost)
    sum_y = sum(i[1] for i in s_ost)
    print(int(abs(sum_x) * 1000 / len(s_ost)), int(abs(sum_y) * 1000 / len(s_ost)))

Ответ: 484 97 870 2128