Задание 27. Информатика. ЕГЭ. Поляков-7657

Просмотры: 91
Изменено: 24 ноября 2024

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками \(A(x_1, \, y_1)\) и \(B(x_2, \, y_2)\) вычисляется по формуле: $$ d(A, \, B) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $$ Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно. Даны два входных файла (файл A и файл Б). В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата \(x\), затем координата \(y\) (в условных единицах). Известно, что количество звёзд не превышает \(1000\). В файле Б хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает \(10~000\). Структура хранения информации о звездах в файле Б аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: \(P_x\) – среднее арифметическое абсцисс центров кластеров, и \(P_y\) – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения \(P_x \times 100~000\), затем целую часть произведения \(P_y \times 100~000\) для файла А, во второй строке – аналогичные данные для файла Б.

Файл с данными

Решение:

Точечная диаграмма, построенная для файла А в табличном процессоре, имеет вид

Видно, что кластеры можно разделит прямыми \(y = -1\), \(x = 1\) и \(x = 3\).

Точечная диаграмма для файла Б, построенная в табличном процессоре, имеет вид

Нижний правый кластер отделяется от остальных прямой \(5y - 6x = -21\). Два других «наезжают» один на другой и точность вычислений зависит от того, как выбрать прямую, которая разрежет эти два кластера. В моём случае — это прямая \(4x + 5y = 17\).

Python (3.10+)


def is_anomaly(point):
    x, y = point
    return (x < 0.5 and y > 3.5) or (x > 6.5 and y > 3) or (x > 5.5 and y < -3.5)

def which_cluster(point, task):
    x, y = point
    match task:
        case 0:
            if y > -1 and x < 3:
                return 0
            elif y < -1 and x > 1:
                return 1
            else:
                return -1
        case 1:
            if 5 * y - 6 * x < -21:
                return 0 if not is_anomaly(point) else -1
            elif 4 * x + 5 * y > 17:
                return 1 if not is_anomaly(point) else -1
            else:
                return 2 if not is_anomaly(point) else -1

def dist(point1, point2):
    x1, y1 = point1
    x2, y2 = point2
    return ((x1 - x2)**2 + (y1 - y2)**2)**0.5

base = ''
files = ['27A.txt', '27B.txt']
clusters = [2, 3]

for t in [0, 1]:
    fd = open(base + files[t])
    fd.readline()
    data = [[], [], []]
    for line in fd:
        x, y = map(float, line.replace(',', '.').split())
        cl = which_cluster([x, y], t)
        if cl > -1:
            data[cl].append([x, y])
    centers = []
    for k in range(clusters[t]):
        dm = 10**100
        c = [0, 0]
        for p in data[k]:
            d = sum(dist(p, pt) for pt in data[k])
            if d < dm:
                dm = d
                c = p
        centers.append(c)
    px = int(sum(c[0] for c in centers) / clusters[t] * 100000)
    py = int(sum(c[1] for c in centers) / clusters[t] * 100000)
    print(px, py)

Ответ:
\(200236\)    \(-98980\)
\(249868\)    \(66357\)