Задание 27 ЕГЭ: кластеризация по порогу R

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

Пример

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

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

Известно, что все звёзды из файла подразделяются ровно на 3 кластера (K = 3) при R = 1,5.

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

Найдите координаты центра кластера с наибольшим количеством звёзд: P_x — абсциссу, P_y — ординату. Гарантируется, что такой кластер единственный.

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

Для справки

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

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

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

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

Решение

Разбиваем звёзды на группы обходом «волной» с R = 1,5: берём любую необработанную звезду и присоединяем к её группе все звёзды не дальше R от уже попавших туда. Получается 3 кластера из 350, 317, 179 звёзд. Кластеры стоят близко друг к другу, поэтому делить их «на глаз» прямой линией рискованно — надёжнее именно обход с заданным R. Группы отсортированы по размеру, поэтому нужный кластер — groups[0].

Ответ: 246913 203314.

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, 1.5)
assert len(groups) == 3
c = center(groups[0])          # группы отсортированы по размеру
print(int(c[0] * 10000), int(c[1] * 10000))

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