Задание 27 ЕГЭ: кластеры: подсчёт звёзд по признакам

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

Пример

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

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

В каждой строке файла 27.txt записана информация об одной звезде: сначала координата x, затем координата y, далее — обозначение звезды. Значения в строке разделены символом табуляции, дробная часть чисел отделяется запятой. Количество строк в файле не превышает 1000. Для звёзд классов светимости I–VI обозначение состоит из спектрального класса (буква, задающая цвет звезды), подкласса (цифра от 0 до 9) и класса светимости (римское число); части обозначения ничем не разделяются, например L9I — оранжевый сверхгигант подкласса 9. Для звёзд класса светимости VII спектральный класс и подкласс не указываются: обозначение — просто VII.

Обозначения цветов и классов светимости:

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

Найдите два числа: Q₁ — количество белых карликов (класс светимости VII), находящихся на расстоянии не более 1,8 от центра своего кластера, и Q₂ — количество зелёных звёзд, находящихся на расстоянии более 1,8 от центра своего кластера (учитываются звёзды всех кластеров).

В ответе запишите два числа: сначала Q₁, затем Q₂.

Для справки

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

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

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

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

Решение

У каждой звезды кластера есть соседка из того же кластера на расстоянии не больше 0,9, а звёзды разных кластеров отстоят друг от друга больше чем на 4; поэтому для разбиения подходит обход «волной» с любым R между этими значениями, например R = 2,0. Кластеры: 308, 150 звёзд. Цвет «зелёный» в этом варианте обозначается буквой G, класс светимости берём из конца обозначения (после буквы и цифры); белые карлики VII записаны без цвета и подкласса, поэтому их проверяем первыми.

Ответ: 33 25.

from math import dist

pts = []                                     # (x, y, обозначение)
for line in open("27.txt"):
    p = line.replace(",", ".").split()
    if p:
        pts.append((float(p[0]), float(p[1]), p[2]))

def parse(mark):                             # (цвет, подкласс, класс светимости)
    if mark == "VII":                        # белый карлик: ни цвета, ни подкласса
        return None, None, "VII"
    return mark[0], int(mark[1]), mark[2:]

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
q1 = q2 = 0
R0 = 1.8
for g in groups:
    c = center(g)
    for a in g:
        color, sub, lum = parse(a[2])
        d = dist(a[:2], c[:2])
        if lum == "VII" and d <= R0:
            q1 += 1
        if color == "G" and d > R0:
            q2 += 1
print(q1, q2)

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