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

Задача . 27_досрок2026_1


Задача

Темы:

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на 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.

 


Статистика успешных решений по компиляторам