Задание 27 ЕГЭ по информатике: решайте с автопроверкой

В задании 27 дан файл с координатами точек на плоскости. Точки образуют группы, кластеры. Нужно найти центр каждого кластера и вычислить по центрам ответ, например средние координаты.

Решать задачи номера

Как решать программой

Сначала разбейте точки на кластеры. Две точки соседние, если расстояние между ними меньше d. Обход в глубину со стеком собирает в один кластер все точки, до которых можно дойти по соседям.

Центр кластера — это точка с наименьшей суммой расстояний до остальных точек кластера. Её находит min с ключом: для каждой точки считается сумма math.dist до всех остальных.

Кластеры из одной точки в задачах обычно считаются аномалиями и отбрасываются. Ответ часто просят умножить на 10 000 и взять целую часть: делайте это в самом конце, чтобы не накопить ошибку округления.

Файлы задания обычно бывают двух видов, A и B. В файле A несколько сотен точек, перебор пар быстрый. В файле B десятки тысяч точек, и полный перебор пар для центров идёт долго, поэтому начинайте с файла A.

Разбор примера

Четыре точки, соседние ближе 1. Три точки образуют кластер, точка (9, 9) одна. Найдём средние координаты центров, умноженные на 10 000.

from math import dist

pts = [(1.2, 1.1), (1.71234, 1.30567), (2.25, 1.1), (9, 9)]
d = 1
clusters, seen = [], set()
for i in range(len(pts)):
    if i in seen:
        continue
    stack, group = [i], []
    seen.add(i)
    while stack:
        j = stack.pop()
        group.append(pts[j])
        for k in range(len(pts)):
            if k not in seen and dist(pts[j], pts[k]) < d:
                seen.add(k)
                stack.append(k)
    if len(group) > 1:
        clusters.append(group)
centers = [min(g, key=lambda p: sum(dist(p, q) for q in g)) for g in clusters]
px = sum(c[0] for c in centers) / len(centers)
py = sum(c[1] for c in centers) / len(centers)
print(int(px * 10000), int(py * 10000))

Программа печатает

17123 13056

Кластер из трёх точек имеет центр (1.71234, 1.30567): сумма расстояний от него до двух других точек меньше, чем у крайних точек. Точка (9, 9) одна и отбрасывается. Центр единственный, поэтому средние равны его координатам.

Решить эту задачу

Задачи к заданию 27

  • Среднее центров кластеровСложнаяРешать
  • Центры самого большого и самого малого кластеровСложнаяРешать
  • Самый дальний центр в пространствеСложнаяРешать
  • Кластеры в городских кварталахСложнаяРешать
  • Центры k кластеров без порогаСложнаяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Как найти кластеры, если они далеко друг от друга?
Обходом по соседям, как в примере. Порог d подберите по рисунку точек или возьмите из условия.
Что делать с аномалиями?
Отбросить кластеры из одной точки, если условие так говорит.
Почему перебор пар медленный на большом файле?
Для 10 000 точек пар 10⁸. Разбейте точки на клетки сетки и сравнивайте только соседние клетки.