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

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

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

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

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

В файле A хранятся данные о звёздах двух квадратов, где $H = 4$ для каждого квадрата. Внутри одного квадрата звёзды определяются к трём кластерам по блеску: $[0,2)$ для первого кластера, $[2,5)$ – для второго и $[5,10]$ – для третьего. В каждой строке файла записана информация о расположении на карте одной звезды, а также об её уровне блеска: сначала координата $x$ , затем координата $y$ и наконец уровень блеска $m$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 2000.

В файле Б хранятся данные о звёздах внутри пяти квадратов, где $H = 2$ для каждого квадрата. Внутри одного квадрата звёзды определяются к двум кластерам по блеску: $[0,5)$ для первого кластера и $[5,15]$ – для второго. Известно, что количество звёзд не превышает 20 000. Структура хранения информации о звездах в файле Б аналогична файлу А.

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

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

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

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

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

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

Рассмотрим 2 квадрата и координаты, которыми их можно последовательно отделить:

1) $x < − 4$

2) все остальные точки

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

file = open("2_A.txt")
file.readline()
kubes = [[[] for j in range(3)] for i in range(2)]
for star in file:
    x, y, m = list(map(float, star.replace(’,’, ’.’).split()))
    if x < -4:
        if 0 <= m < 2:
            kubes[0][0].append((x, y))
        if 2 <= m < 5:
            kubes[0][1].append((x, y))
        if 5 <= m <= 10:
            kubes[0][2].append((x, y))
    else:
        if 0 <= m < 2:
            kubes[1][0].append((x, y))
        if 2 <= m < 5:
            kubes[1][1].append((x, y))
        if 5 <= m <= 10:
            kubes[1][2].append((x, y))

p_x = p_y = 1
for kube in kubes:
    s_x = s_y = 0
    for cluster in kube:
        tx = ty = 0
        mn = 10**20
        for centroid in cluster:
            x1, y1 = centroid
            sm = 0
            for star in cluster:
                x2, y2 = star
                sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
            if sm < mn:
                mn = sm
                tx, ty = x1, y1
        s_x += tx
        s_y += ty
    p_x *= s_x / 3
    p_y *= s_y / 3

print(int(p_x * 100))
print(int(p_y * 100))

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

Рассмотрим 5 квадратов и координаты, которыми их можно последовательно отделить:

1) $x < − 7$

2) $x < − 2$

3) $x < 3$

4) $x < 6$

5) все остальные точки

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

file = open("2_B.txt")
file.readline()
kubes = [[[] for j in range(2)] for i in range(5)]
for star in file:
    x, y, m = list(map(float, star.replace(’,’, ’.’).split()))
    if x < -7:
        if 0 <= m < 5:
            kubes[0][0].append((x, y))
        if 5 <= m <= 15:
            kubes[0][1].append((x, y))
    elif x < -2:
        if 0 <= m < 5:
            kubes[1][0].append((x, y))
        if 5 <= m <= 15:
            kubes[1][1].append((x, y))
    elif x < 3:
        if 0 <= m < 5:
            kubes[2][0].append((x, y))
        if 5 <= m <= 15:
            kubes[2][1].append((x, y))
    elif x < 6:
        if 0 <= m < 5:
            kubes[3][0].append((x, y))
        if 5 <= m <= 15:
            kubes[3][1].append((x, y))
    else:
        if 0 <= m < 5:
            kubes[4][0].append((x, y))
        if 5 <= m <= 15:
            kubes[4][1].append((x, y))

p_x = p_y = 1
for kube in kubes:
    s_x = s_y = 0
    for cluster in kube:
        tx = ty = 0
        mn = 10**20
        for centroid in cluster:
            x1, y1 = centroid
            sm = 0
            for star in cluster:
                x2, y2 = star






































































































































































































                sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
            if sm < mn:
                mn = sm
                tx, ty = x1, y1
        s_x += tx
        s_y += ty
    p_x *= s_x / 2
    p_y *= s_y / 2

print(int(p_x / 10))
print(int(p_y / 10))

Ответ: -160 -914 117 -190