Задание выполняется с использованием прилагаемых файлов.
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на 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=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество точек не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H=7, W=3 для каждого кластера. Известно, что количество точек не превышает \(10\,000\). Структура хранения информации о звездах в файле Б аналогична файлу А.
Известно, что в файле А и Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров.
Для файла А определите координаты центра каждого кластера, затем вычислите два числа: A1 — суммарное расстояние между центром кластера с наибольшим количеством точек до всех аномалий, и A2 — суммарное расстояние между центром кластера с наименьшим количеством точек до всех аномалий.
Для файла Б определите координаты центра каждого кластера, затем вычислите два числа: B1 — максимальное возможное суммарное расстояние от одного центра кластера до всех аномалий, и B2 — минимальная возможная площадь прямоугольника (со сторонами, параллельными координатным осям), на сторонах которого будут лежать все центры кластеров.
Гарантируется, что во всех кластерах обоих файлов количество точек различно.
В ответе запишите четыре числа: в первой строке — сначала целую часть произведения A1 × \(10\,000\), затем целую часть произведения A2 × \(10\,000\); во второй строке — сначала целую часть произведения B1 × \(10\,000\), затем целую часть произведения B2 × \(10\,000\).