Задача #3574

(Иглин К.) Учёный наблюдает проекцию звёздного скопления на плоскость с декартовой системой координат. Полученные точки (звёзды) необходимо разбить на N непересекающихся непустых кластеров. Каждый кластер размещается внутри прямоугольника размером H x W, при этом прямоугольники не перекрываются. Стороны прямоугольников не обязаны быть параллельны осям координат. Гарантируется, что такое разбиение единственно для заданных размеров прямоугольников. Расстояние между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле:

$D(A,B)=\sqrt{(x_2-x_1{)}^2+(y_1-y_2{)}^2}$​

Антицентром кластера будем называть точку кластера, сумма расстояний от которой до остальных точек этого кластера максимальна.

В файле А храняться координаты точек двух кластеров, где H = 6,5 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначало координата $x$, затем координата $y$. Известно, что количество точек не превышает 1000.
В файле Б хранятся координаты точек трёх кластеров, где H = 5, W = 4,5 для каждого кластера. Известно, что количество точек не превышает 10000. Структура хранения информации в файле Б аналогична структуре в файле А.

Известно, что в файле А имеются координаты ровно трёх, а в файле Б ровно четырёх "лишних" точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты антицентра каждого кластера, затем найдите два числа: $P_x$ - максимальную абсциссу антицентра кластера и $P_y$ - максимальную ординату антицентра кластера.

Для файла Б определите координаты антицентра каждого кластера, затем найдите два числа: $Q_1$ - расстояние между антицентрами кластеров с минимальным и максимальным количеством точек и $Q_2$ - максимальное расстояние от антицентра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите 4 числа: а первой строке - сначала целую часть абсолютной величины произведения $P_x$ $\times 10000$, затем целую часть абсолютной величины произведения $P_y$ $\times 10000$; во второй строке - сначала целую часть произведения $Q_1$$\times 10000$, затем целую часть произведения $Q_2$$\times 10000$.

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