Олимпиадный тренинг

Задача . 27_сред2026_2


Задача

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

Для каждой звезды дана характеристика: тип цвета, тип светимости и её размер в соответствии с искомой таблицей.
Обозначение Цвет Обозначение Размер
G белый I сверхгигант
J зелёный II яркий гигант
L синий III гигант
N оранжевый IV субгигант
Y красный V карлик
S голубой VI субкарлик
Z жёлтый VII белый карлик
Полученные значения записаны в характеристике слитно: обозначение цвета, светимость (обозначается арабской цифрой) и обозначение размера планеты.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. 
В файле A хранятся данные о звёздах двух кластеров, где H=6,5, W=4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y, а затем характеристика звезды. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H=6,5, W=5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А. 
Для файла А определите координаты центра каждого кластера, затем найдите два числа: A1​ – минимальное расстояние от центра
кластера с наибольшим количеством точек до жёлтого яркого гиганта, и A2​ – максимальное расстояние от центра кластера с наименьшим количеством точек до жёлтого яркого гиганта.

Для файла Б определите координаты центра каждого кластера, затем найдите два числа: B1​ – сумма расстояний между двумя различными синими карликами, расположенными в кластере с максимальным количеством точек, и B2​ – расстояние между центрами кластеров с минимальным и медианным количеством синих карликов.
В ответе запишите четыре числа: в первой строке – сначала целую часть произведения A1​ × 10 000, затем целую часть произведения A2​ × 10 000; во второй строке – сначала целую часть абсолютного значения произведения B1​ × 10 000, затем целую часть абсолютного значения произведения B2​ × 10 000.
 
Статистика успешных решений по компиляторам