Задание 27 ЕГЭ 2027 по информатике: центры кластеров

Самостоятельный практикум по поиску центров двух кластеров. Скачайте файл с точками, получите две координаты и проверьте строку ответа.

Скачать 27-clusters.txt

Это авторская тренировка одного навыка: граница кластеров задана. Формат строки из двух чисел соответствует инструкции 2027.

Задания

1Авторская задача

Файл содержит координаты точек без заголовка. К первому кластеру относятся точки с x < 50, остальные — ко второму. Центр каждого кластера — его точка, у которой сумма евклидовых расстояний до всех точек этого кластера минимальна. При равенстве берите точку с меньшим x, затем с меньшим y. Усредните x двух центров, отдельно усредните y. Умножьте обе средние координаты на 10 000 и запишите целые результаты в одной строке.

Решение

Нельзя заменить центр кластера средним арифметическим всех точек: он должен быть точкой из файла. Задаём кластер по условию, перебираем кандидатов центра и считаем стоимость по евклидову расстоянию. Усреднение выполняем после поиска двух центров. Координаты читаем в целых сотых, поэтому умножение суммы на 50 сразу даёт требуемый результат.

from math import hypot
from pathlib import Path
from decimal import Decimal
points = []
for line in Path("27-clusters.txt").read_text().splitlines():
    x, y = map(Decimal, line.split())
    points.append((int(x * 100), int(y * 100)))

def center(group):
    def cost(p):
        x, y = p
        return sum(hypot(x - a, y - b) for a, b in group), p
    return min(group, key=cost)

a = center([p for p in points if p[0] < 5000])
b = center([p for p in points if p[0] >= 5000])
print((a[0] + b[0]) * 50, (a[1] + b[1]) * 50)

Дальше по теме

Источники