EGEsoll - сборник решений задач из ЕГЭ

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Для каждой звезды дана характеристика: тип цвета, тип светимости и её размер в соответствии с искомой таблицей.

Обозначение	Цвет	Обозначение	Размер
G	белый	I	сверхгигант
J	зелёный	II	яркий гигант
L	синий	III	гигант
N	оранжевый	IV	субгигант
Y	красный	V	карлик
S	голубой	VI	субкарлик
Z	жёлтый	VII	белый карлик

Полученные значения записаны в характеристике слитно: обозначение цвета, светимость (обозначается арабской цифрой) и обозначение размера планеты.

В файле B хранятся данные о звёздах трёх кластеров, где H=6,5, W=5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А. 

Для файла Б определите координаты центра каждого кластера, затем найдите два числа: B1 – минимальное расстояние между двумя различными жёлтыми сверхгигантами, расположенными в одном и том же кластере, и B2 – расстояние между центрами кластеров с минимальным и максимальным количеством жёлтых сверхгигантов.

В ответе запишите четыре числа: в первой строке – сначала целую часть произведения B1 * 10 000, затем целую часть абсолютного значения произведения B2 * 10 000.

Из-за технических ограничений сайта для скачивания доступен один файл - B.

Досрочный вариант 2026 - КЕГЭ

Download File 1

Добавлено: 20.04.26 20:43

Перейти к решению

from math import dist

def dist_w(star1, star2):
    dot1 = star1[:2]
    dot2 = star2[:2]
    return dist(dot1, dot2)

def center(cl):
    best = []
    minsum = 10**20
    for star in cl:
        summ = sum(dist_w(star, star1) for star1 in cl)
        if summ < minsum:
            minsum = summ
            best = star
    return best

def cluster(star):
    cl = [star1 for star1 in sky if dist_w(star, star1)<1]
    if len(cl) > 0:
        for star1 in cl:
            sky.remove(star1)
        newcl = [cluster(star1) for star1 in cl]
        for x in newcl: cl += x         
    return cl

sky = []
for s in open("embed.txt"):
    s = s.replace(",", ".")
    st = s.split()
    x, y, = map(float, st[:2])
    sky.append([x,y, st[2]])

clusterB = []
while len(sky) > 0:
    cl = cluster(sky[0])
    clusterB.append(cl)


centroidsB = [center(cl) for cl in clusterB]
for cl in clusterB:
    if len([star for star in cl if star[2][0] == "Z" and star[2][2:] == "I"]) > 2:
        d = int(min([dist_w(star1, star2) for star1 in cl if star1[2][0] == "Z" and star1[2][2:] == "I" for star2 in cl if star2[2][0] == "Z" and star2[2][2:] == "I" and star2 != star1])*10000)
        print("потенциальное б1:", d)
print("б2: ", int(dist_w(centroidsB[0], centroidsB[1])*10000))

потенциальное б1: 1035
потенциальное б1: 1962
б2:  125591