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

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

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

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

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

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

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

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

В ответе запишите четыре числа через пробел: сначала целую часть произведения $P ⋅333 x$ для файла А и $Py ⋅666$ для файла А, далее целую часть произведения $Px ⋅321$ для файла Б и $Py ⋅123$ для файла Б.

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

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

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

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

Рассмотрим подробно нижний кластер. Он симметричен относительно оси Oy и Ox. Его радиус равен $3$ . Следовательно, если координаты точки удовлетворяют неравенству окружности: $x2 + y2 ≤ 9$ , значит, это точка принадлежит нижнему кластеру.

Изучим верхний внутренний кластер, его радиус равен $2$ . Центр круга находится в точке (-5;4). Следовательно, если координаты точки удовлетворяют неравенству окружности: $(x +5)2 + (y− 4)2 ≤ 4$ , значит, это точка принадлежит верхнему внутреннему кластеру.

Если точка не удовлетворяет ни одному из выше описанных неравенств, значит, она находится во внешнем кластере (кольце). Поскольку мы не высчитываем центроид колец, то данные точки нас не интересуют.

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

f = open(’27_4_A.txt’)
n = f.readline()
clusters = [[] for i in range(2)]
for i in range(966):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    x,y = star[0],star[1]
    if x**2 + y ** 2 <= 9:
        clusters[0].append(star)
    elif (x + 5)**2 + (y - 4) ** 2 <= 4:
        clusters[1].append(star)
sum_x = sum_y = tx = ty = 0
for i in clusters:
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(sum_x / len(clusters) * 333))
print(int(sum_y / len(clusters) * 666))

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

Разберем подробнее нижний правый кластер. Центр круга находится в точке (1;-1). Его радиус равен $3$ . Следовательно, если координаты точки удовлетворяют неравенству окружности: $(x− 1)2 + (y+ 1)2 ≤ 9$ , значит, это точка принадлежит нижнему правому кластеру.

Изучим поподробнее нижний левый кластер. Центр круга находится в точке (-5;-5). Его радиус равен $4$ . Следовательно, если координаты точки удовлетворяют неравенству окружности: $(x+ 5)2 + (y+ 5)2 ≤ 16$ , значит, это точка принадлежит нижнему левому кластеру.

Рассмотрим верхний внутренний кластер. Центр круга находится в точке (-6;3). Его радиус равен $2$ . Следовательно, если координаты точки удовлетворяют неравенству окружности: $(x+ 6)2 + (y− 3)2 ≤ 4$ , значит, это точка принадлежит верхнему внутреннему кластеру.

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

f = open(’27_4_B.txt’)
n = f.readline()
clusters = [[] for i in range(3)]
for i in range(4798):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    x,y = star[0],star[1]
    if ((x - 1) ** 2 + (y  + 1) ** 2) <= 9:
        clusters[0].append(star)
    elif ((x - (-6)) ** 2 + (y - 3) ** 2) <= 4:
        clusters[1].append(star)
    elif ((x + 5)**2 + (y + 5)**2) <= 16:
        clusters[2].append(star)
sum_x = sum_y = tx = ty = 0
for i in clusters:
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(sum_x / len(clusters) * 321))
print(int(sum_y / len(clusters) * 123))

Ответ: -800 1274 -1081 -120