Задание №27

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

Будем называть межкластерным диаметром двух кластеров максимальное расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая – другому. Для каждой пары кластеров гарантируется, что межкластерный диаметр образует единственная пара точек. Расстояние между двумя точками на плоскости A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:

\( d(A,B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \).

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

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

Известно, что в файле Б имеются координаты ровно четырёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти четыре точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для обоих файлов определите межкластерные диаметры для каждой пары различных кластеров. Для файла A найдите два числа: P_x – модуль разности абсцисс точек, образующих межкластерный диаметр, и P_y – сумму ординат точек, образующих межкластерный диаметр. Для файла Б найдите два числа: Q₁ – сумму всех межкластерных диаметров и Q₂ – максимальное расстояние от какой-либо точки, образующей межкластерный диаметр, до точки с координатами (1, 1).

В ответе запишите четыре числа: в первой строке – сначала целую часть произведения P_x × 1000, затем целую часть абсолютного значения произведения P_y × 1000; во второй строке – сначала целую часть произведения Q₁ × 100, затем целую часть произведения Q₂ × 100.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.