Красные гиганты, оранжевые гиганты, жёлтые карлики

Фрагмент звёздного неба спроецирован на плоскость. Точки нужно разбить на N непересекающихся кластеров так, что точки каждого кластера лежат внутри прямоугольника со сторонами H и W (стороны не обязательно параллельны осям), прямоугольники не пересекаются; разбиение существует и единственно. Центр кластера — его звезда, сумма расстояний от которой до всех остальных звёзд кластера минимальна (центр единственен). Каждая звезда помимо координат характеризуется спектральным классом и классом светимости. Спектральный класс (буква) определяет цвет: O — голубой, B — бело-голубой, A — белый, F — жёлто-белый, G — жёлтый, K — оранжевый, M — красный; за буквой идёт подкласс от 0 до 9. Классы светимости: I — сверхгигант, II — яркий гигант, III — гигант, IV — субгигант, V — карлик, VI — субкарлик, VII — белый карлик. В строке файла: координаты x и y, затем (для классов светимости I–VI) спектральный класс, подкласс и класс светимости без разделителей, например G2V; для белых карликов указано только VII. Файл A: два кластера, H = 6,0, W = 5,5, не больше 2000 точек. Файл Б: три кластера, H = 6,0, W = 5,5, не больше 10 000 точек. Для файла А найдите Ax и Ay — абсциссу и ординату красного гиганта, ближайшего к центру кластера, который содержит наименьшее количество точек. Для файла Б найдите B1 — расстояние между центрами кластеров с наименьшим и наибольшим количеством оранжевых гигантов и B2 — наибольшее расстояние между жёлтыми карликами одного кластера. В ответе запишите четыре числа: в первой строке — целую часть |Ax × 10 000|, затем целую часть |Ay × 10 000|; во второй строке — целую часть B1 × 10 000, затем целую часть B2 × 10 000.

Источник: ФИПИ (Открытый вариант 2026)

Скачать файл: main2026_27_A.txt, main2026_27_B.txt. В редакторе он уже лежит рядом с кодом, открывай как на экзамене: open('main2026_27_A.txt').