Войти
или
Зарегистрироваться
Маркетплейс
Курсы
Учебник
Учебник 2.0
ЕГЭ
ОГЭ
Олимпиады
Рубрикатор
Компилятор
Онлайн Компилятор
Компилятор Python с отладкой
Питон - Черепашка
Эмулятор исполнителя Робот - Кумир
Редактор HTML Code
SQLite Studio - работа с БД
Клавиатурный тренажёр программиста
Олимпиадный тренинг
Задача
.
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 аналогична файлу А.
Для файла А определите координаты центра каждого кластера, затем найдите два числа:
A
1
– минимальное расстояние от центра
кластера с наибольшим количеством точек до жёлтого яркого гиганта, и
A
2
– максимальное расстояние от центра кластера с наименьшим количеством точек до жёлтого яркого гиганта.
Для файла Б определите координаты центра каждого кластера, затем найдите два числа:
B
1
– сумма расстояний между двумя различными синими карликами, расположенными в кластере с максимальным количеством точек, и
B
2
– расстояние между центрами кластеров с минимальным и медианным количеством синих карликов.
В ответе запишите четыре числа: в первой строке – сначала целую часть произведения
A
1
× 10 000, затем целую часть произведения
A
2
× 10 000; во второй строке – сначала целую часть абсолютного значения произведения
B
1
× 10 000, затем целую часть абсолютного значения произведения
B
2
× 10 000.
1000
ms
256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач
Статистика успешных решений по компиляторам