Оранжевые субкарлики и центры кластеров

Фрагмент звёздного неба спроецирован на плоскость. Точки нужно разбить на 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 звёзд. Для файла А найдите A1 — наименьшее расстояние от оранжевого субкарлика до центра кластера, к которому он относится, и A2 — суммарное расстояние от центров кластеров до точки (−1,5; −1,5). Для файла Б найдите B1 — абсциссу и B2 — ординату центра кластера с наименьшим количеством оранжевых субкарликов. В ответе запишите четыре числа: в первой строке — целую часть A1 × 10 000, затем целую часть A2 × 10 000; во второй строке — целую часть |B1 × 10 000|, затем целую часть |B2 × 10 000|.

Источник: ФИПИ (Резерв 22.06.2026), № 31233

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