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

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри шара радиусом $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 = 3$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ , затем координата $z$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 1000.

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

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

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

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

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

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

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

Из графика видно, что один кластер имеет положительные координаты $(x,y)$ , а другой отрицательные. Пользуясь этим знанием, разделим данные на кластеры в программе.

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

from math import *

f = open("A.txt")
n = f.readline()
a = [[] for i in range(2)]
for i in range(890 - 1):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    if star[0] > 0 and star[1] > 0:
        a[0].append(star)
    else:
        a[1].append(star)

sum_x = sum_y = sum_z = tx = ty = tz = 0

for i in a:
    mn = 100000050000
    for zvezda_1 in i:
        sm = 0
        for zvezda_2 in i:
            sm += dist(zvezda_1, zvezda_2)
        if sm < mn:
            mn = sm
            tx, ty, tz = zvezda_1
    sum_x += tx
    sum_y += ty
    sum_z += tz

print(int(sum_x / 2 * 1000))
print(int(sum_y / 2 * 1000))
print(int(sum_z / 2 * 1000))

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

Из графика видно, что один кластер имеет только отрицательные координаты $(x,y)$ , у другого координата $x$ только отрицательная, а $y$ больше 7. Пользуясь этим знанием, разделим данные на кластеры в программе.

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

from math import *

f = open("B.txt")
n = f.readline()
a = [[] for i in range(3)]
for i in range(9320 - 1):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    if star[0] < 0 and star[1] < 0:
        a[0].append(star)
    elif star[0] < 0 and star[1] > 7:
        a[1].append(star)
    else:
        a[2].append(star)

sum_x = sum_y = sum_z = tx = ty = tz = 0

for i in a:
    mn = 100000050000
    for zvezda_1 in i:
        sm = 0
        for zvezda_2 in i:
            sm += dist(zvezda_1, zvezda_2)
        if sm < mn:
            mn = sm
            tx, ty, tz = zvezda_1
    sum_x += tx
    sum_y += ty
    sum_z += tz

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

Ответ: 209 37 -38 -2415 2822 1242