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

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

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

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

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

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

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

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

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

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

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

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

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

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

Код для файла А

from math import *

def dist_3d(p1, p2): # Расстояние между точками в декартовой системе координат
    return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2 + (p1[2] - p2[2])**2) ** 0.5

def dbscan(a, r):
    cl = [] # Инициализируем список для хранения кластеров
    while a: # Пока есть элементы в входном массиве ’a’
        cl.append([a.pop(0)])
        for i in cl[-1]: # Проходим по элементам последнего кластера
            for j in a[:]:
                if dist_3d(i, j) <= r:
                    cl[-1].append(j) # Добавляем ’j’ в текущий кластер
                    a.remove(j) # Удаляем ’j’ из списка ’a’, чтобы не проверять его снова
    return cl

f = open("4_A.txt")
s = f.readline()
a = [list(map(float, i.replace(",", ".").split())) for i in f]
cl = dbscan(a, 0.8) # Для файла А
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_3d(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) / 10))

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

Код для файла Б

from math import *

def dist_3d(p1, p2): # Расстояние между точками в декартовой системе координат
    return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2 + (p1[2] - p2[2])**2) ** 0.5

def dbscan(a, r):
    cl = [] # Инициализируем список для хранения кластеров
    while a: # Пока есть элементы в входном массиве ’a’
        cl.append([a.pop(0)])
        for i in cl[-1]: # Проходим по элементам последнего кластера
            for j in a[:]:
                if dist_3d(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, 0.9) # Для файла Б
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_3d(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) * 100))

Ответ: 81560 68