Задача к ЕГЭ по информатике на тему «Анализ данных (звезды)» №3

Лосяш решил исследовать звёздное небо над Долиной Смешариков. Он провёл кластеризацию множества звёзд по их расположению на трёхмерной карте. Кластер звёзд — это набор точек на графике, каждая из которых находится от хотя бы одной другой звезды на расстоянии не более $R$ условных единиц. Каждая звезда принадлежит только одному кластеру.

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

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

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

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

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

В файле B хранятся данные о звёздах двух кластеров, где $R = 0.7$ для каждого кластера. Количество звёзд не превышает 5200. Структура данных в файле B аналогична файлу A.

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

В ответе запишите два числа через пробел: сначала целую часть частного $Pxyz- 5$ для файла A, затем целую часть произведения $Pxyz ⋅50$ для файла B.

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

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

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

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

Для разделения звёзд на кластеры используем алгоритм DBSCAN с соответствующими радиусами. Затем для каждого кластера определим центроид, вычислив сумму расстояний от каждой звезды до остальных и выбрав звезду с минимальной суммой. После этого рассчитаем $Pxyz$ как квадрат произведения средних координат центроидов.

Код для файла 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("3_A.txt")
a = [list(map(float, i.replace(",", ".").split())) for i in f]
cl = dbscan(a, 1.5)  # Для файла А
cl_total = []
for i in cl:
    if len(i) > 50: 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) / 5))

Код для файла B:

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("3_B.txt")
a = [list(map(float, i.replace(",", ".").split())) for i in f]
cl = dbscan(a, 0.7)
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 / 2 * sum_y / 2 * sum_z / 2) ** 2) * 50))

Ответ: 1113 24998079