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

Задача . 27_апроб2026_1


Задача

Темы:

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

В файле A хранятся данные о звёздах двух кластеров, где H=6,5, W=4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров, где H=6,5, W=5 для каждого кластера. Известно, что количество звёзд не превышает 1000. Структура хранения информации о звездах в файле B аналогична файлу А. 

Для файла А определите координаты центра каждого кластера, затем найдите два числа: A1 -  максимальное количество точек в кластере и A2​ - cумму расстояний от центров кластеров до точки с координатами (1,0; 1,5).

Для файла Б определите координаты центра каждого кластера, затем найдите два числа: B1 - число точек, находящихся на расстоянии не более 1,2 от центра, не включая центр, в кластере со средним количеством точек, и B2​ - минимальное расстояние от центра кластера с наибольшим количеством точек до другой точки этого кластера.
Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке - сначала A1, затем целую часть произведения A2​ × 10 000; во второй строке - сначала B1, затем целую часть произведения B2 × 10 000.


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