Задача #3296

(Д. Бахтиев) Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества находятся внутри прямоугольника со сторонами длиной H и W, причём прямоугольники не пересекаются между собой. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера такую его точку, сумма расстояний от которой до всех остальных точек кластера минимальна, а плотностью кластера — отношение числа звёзд в нём к площади прямоугольника (в у.е.), внутри которого этот кластер находится. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости
A(x1, y1) и B(x2, y2) вычисляется по формуле: $d=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$.​
В файле A хранятся данные о звёздах трёх кластеров, где H = 4, W = 4 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах пяти кластеров, где H = 4, W = 4 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите $Ps$ — среднее арифметическое плотности всех кластеров, а также $Sp$ — расстояние между центрами кластеров с наибольшей и наименьшей плотностью.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения $Ps·1000$, затем целую часть произведения $Sp·1000$ для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.