Задание выполняется с использованием прилагаемых файлов.
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Расстояние между двумя точками на плоскости \( A(x_1, y_1) \) и \( B(x_2, y_2) \) вычисляется по формуле: \( d(A,B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \).
В файле А хранятся данные о звёздах двух кластеров, где H=6, W=6 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество точек не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H=4, W=6 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А вычислите два числа: \( A_1 \) – минимальное расстояние между двумя различными точками, принадлежащими кластеру с наибольшим количеством точек, и \( A_2 \) – максимальное расстояние между двумя точками, принадлежащими кластеру с наименьшим количеством точек.
Для файла Б вычислите два числа: \( B_1 \) – минимальное суммарное расстояние между тремя точками, принадлежащими трём различным кластерам, и \( B_2 \) – максимальное суммарное расстояние между тремя точками, принадлежащими трём различным кластерам.
В ответе запишите четыре числа: в первой строке – сначала целую часть произведения \( A_1 \times 10000 \), затем целую часть произведения \( A_2 \times 10000 \); во второй строке – сначала целую часть произведения \( B_1 \times 10000 \), затем целую часть произведения \( B_2 \times 10000 \).