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

Просмотры: 257
Изменено: 1 февраля 2025

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками A(x1,y1) и B(x2,y2) вычисляется по формуле: d(A,B)=(x1x2)2+(y1y2)2 Даны два входных файла (файл A и файл Б). В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (в условных единицах). Известно, что количество звёзд не превышает 1000. В файле Б хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px×10 000, затем целую часть произведения Py×10 000 для файла А, во второй строке – аналогичные данные для файла Б.

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

Решение:

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

Видно, что два кластера отчётливо разделяются прямой, проходящей через точки M(2,0) и N(0,4). Уравнение прямой, проходящей через них, имеет вид 2x+y=4.

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

Правый верхний кластер можно отделить прямой, проходящей через точки M(8,4.5) и N(4,10.5). Уравнение прямой, проходящей через них, имеет вид 3x+2y=33. Остальные два кластера разделяются прямой, проходящей через точки P(2.5,5) и Q(6,9.5). Уравнение прямой, проходящей через них, имеет вид 7y9x=12.5.

Python (3.10+)


def which_cluster(point, task):
    x, y = point
    match task:
        case 0:
            return int(2 * x +  y > 4)
        case 1:
            if 3 * x + 2 * y > 33:
                return 0
            elif 7 * y - 9 * x > 12.5:
                return 1
            return 2

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())
        data[which_cluster([x, y], t)].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] * 10000)
    py = int(sum(c[1] for c in centers) / clusters[t] * 10000)
    print(px, py)

Ответ:
531732715
5308878127