Задание 27 ЕГЭ: кластеры: средние и попарные расстояния

Средние и попарные расстояния в кластерах. Тема номера — кластеризация данных. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

Учёный-астроном анализирует карту звёздного неба. Звёзды на карте образуют кластеры — компактные группы; каждая звезда принадлежит ровно одному кластеру, а кластеры расположены далеко друг от друга — гораздо дальше, чем соседние звёзды одного кластера. Центр кластера — это одна из звёзд кластера, сумма расстояний от которой до всех остальных звёзд этого кластера минимальна. Для каждого кластера центр единственен.

В файле записаны координаты звёзд двух кластеров.

В каждой строке файла 27.txt записана информация об одной звезде: сначала x, затем y. Значения в строке разделены символом табуляции, дробная часть чисел отделяется точкой. Количество строк в файле не превышает 1000.

Для каждого кластера найдите среднее арифметическое расстояний от его центра до всех остальных звёзд этого кластера. Найдите Q₁ — наименьшее, и Q₂ — наибольшее из полученных значений.

В ответе запишите два числа: сначала целую часть произведения Q₁ × 10 000, затем целую часть произведения Q₂ × 10 000.

Для справки

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂) на плоскости вычисляется по формуле

d(A, B) = √((x₂ − x₁)² + (y₂ − y₁)²).

Запишите два числа через пробел.

Скачать файл к примеру

Решение

У каждой звезды кластера есть соседка из того же кластера на расстоянии не больше 0,9, а звёзды разных кластеров отстоят друг от друга больше чем на 4; поэтому для разбиения подходит обход «волной» с любым R между этими значениями, например R = 2,0. Кластеры: 336, 193 звёзд. Среднее — по остальным звёздам, то есть делим на (размер кластера − 1); расстояние от центра до самого себя равно нулю и в сумму ничего не добавляет.

Ответ: 19882 26446.

from math import dist

pts = []
for line in open("27.txt"):
    p = line.replace(",", ".").split()      # запятая → точка; split() понимает и табуляции
    if p:
        pts.append((float(p[0]), float(p[1])))

def clusters(pts, R):
    """Разбиение: звёзды, соединённые цепочкой шагов не длиннее R, — в одной группе."""
    rest, groups = pts[:], []
    while rest:
        group = [rest.pop()]
        for a in group:                      # group растёт по ходу цикла — обход в ширину
            near = [b for b in rest if dist(a[:2], b[:2]) <= R]
            if near:
                rest = [b for b in rest if dist(a[:2], b[:2]) > R]
                group += near
        groups.append(group)
    return sorted(groups, key=len, reverse=True)     # от большего кластера к меньшему

def center(g):                               # звезда с наименьшей суммой расстояний до остальных
    return min(g, key=lambda a: sum(dist(a[:2], b[:2]) for b in g))

groups = clusters(pts, 2.0)
assert len(groups) == 2
avg = []
for g in groups:
    c = center(g)
    avg.append(sum(dist(c[:2], a[:2]) for a in g) / (len(g) - 1))   # сам центр даёт 0
print(int(min(avg) * 10000), int(max(avg) * 10000))

Решить такую задачу — новый вариант с проверкой