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

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

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

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

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

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

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

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

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

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

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

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

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

Из графика видно, что один кластер имеет абсциссы, меньшие 40.

Второй кластер имеет ординаты, меньшие 100, а абсциссы от 60 до 100.

Третий кластер имеет абсциссы, большие 130, а четвертый – все остальные. Пользуясь этим знанием, разделим данные на кластеры в программе.

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

from math import *
f = open(’5_A.txt’)
n = f.readline()

clusters = [[] for i in range(4)]
for i in f:
    star = list(map(float, i.replace(’,’, ’.’).split()))
    if star[0] < 40:
        clusters[0].append(star)
    elif 60 < star[0] < 100 and star[1] < 100:
        clusters[1].append(star)
    elif star[1] > 130:
        clusters[2].append(star)
    else:
        clusters[3].append(star)
sum_x = sum_y = sum_z = tx = ty = tz = 0

for cluster in clusters:
    mn = 10**20
    for star_1 in cluster:
        sm = 0
        for star_2 in cluster:
            sm += dist(star_1,star_2)
        if sm < mn:
            mn = sm
            tx,ty,tz = star_1
    sum_x += tx
    sum_y += ty
    sum_z += tz
print(int((sum_x/4+sum_y/4+sum_z/4)**0.5))

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

Из графика видно, что шесть кластеров распределены следующим образом:

1. Первый имеет абсциссы меньшие 60

2. Второй абсциссы от 70 до 90, а ординаты от 70

3. Третий абсциссы от 80 до 100, а ординаты меньшие 65

4. Четвертый ординаты от 140 и абсциссы меньшие 135

5. Пятый все остальные точки

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

from math import *
f = open(’5_B.txt’)
n = f.readline()

clusters = [[] for i in range(5)]
for i in f:
    star = list(map(float, i.replace(’,’, ’.’).split()))
    if star[0] < 60:
        clusters[0].append(star)
    elif 70 < star[0] < 90 and star[1] > 70:
        clusters[1].append(star)
    elif 80 < star[0] < 100 and star[1] < 65:
        clusters[2].append(star)
    elif star[0] < 135 and star[1] > 140:
        clusters[3].append(star)
    else:
        clusters[4].append(star)
sum_x = sum_y = sum_z = tx = ty = tz = 0
for cluster in clusters:
    mn = 10**20
    for star_1 in cluster:
        sm = 0
        for star_2 in cluster:
            sm += dist(star_1,star_2)
        if sm < mn:
            mn = sm
            tx,ty,tz = star_1
    sum_x += tx
    sum_y += ty
    sum_z += tz
print(int((sum_x/5+sum_y/5+sum_z/5)**0.5))

Ответ: 17 16