N непересекающихся непустых подмножеств (кластеров), таких, что точки

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на 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 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Файл АФайл БСтруктура хранения информации о звёздах в файле Б аналогична структуре в файле A.Известно, что в файле Б имеются координаты ровно четырёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти четыре точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для обоих файлов определите межкластерные диаметры для каждой пары различных кластеров. Для файла А найдите два числа: Pₓ — модуль разности абсцисс точек, образующих межкластерный диаметр и P_y - сумму ординат точек, образующих межкластерный диаметр. Для файла Б найдите два числа: Q₁ — сумму всех межкластерных диаметров и Q₂ — максимальное расстояние от какой-либо точки, образующей межкластерный диаметр, до точки с координатами (1, 1). В ответе запишите четыре числа: в первой строке - сначала целую часть произведения Pₓ × 1000, затем целую часть абсолютного значения произведения P_y × 1000; во второй строке - сначала целую часть произведения Q₁ × 100, затем целую часть произведения Q₂ × 100. Возможные данные одного из файлов иллюстрированы графиком.

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

Для выполнения задания используйте данные из прилагаемого файла.

Ответ: