Задание выполняется с использованием прилагаемых файлов.
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на 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=7, W=5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество точек не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H=7, W=4 для каждого кластера. Известно, что количество точек не превышает 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 \).