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

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

Пример

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

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

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

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

Найдите два числа: P₁ — наибольшее, и P₂ — наименьшее из расстояний между центрами кластеров (рассматриваются все пары кластеров).

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

Для справки

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

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

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

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

Решение

У каждой звезды кластера есть соседка из того же кластера на расстоянии не больше 0,9, а звёзды разных кластеров отстоят друг от друга больше чем на 4; поэтому для разбиения подходит обход «волной» с любым R между этими значениями, например R = 2,0. Кластеры: 329, 310, 83 звёзд, плюс 2 одиночные точки-аномалии — их отбрасываем. Находим центры и перебираем все пары центров.

Ответ: 292763 137232.

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)
groups = [g for g in groups if len(g) > 1]   # одиночки — аномалии
assert len(groups) == 3
cs = [center(g) for g in groups]
d = [dist(a, b) for i, a in enumerate(cs) for b in cs[i + 1:]]
print(int(max(d) * 10000), int(min(d) * 10000))

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