Задание №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.

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

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

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

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

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