Задание 27 ЕГЭ по информатике

Учёный наблюдает проекцию звёздного скопления на плоскость с декартовой системой координат. Полученные точки (звёзды) необходимо разбить на $N$ непересекающихся непустых кластеров. Каждый кластер размещается внутри прямоугольника размером $H$ на $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.

В файле B хранятся координаты точек трёх кластеров, где $H = 5$, $W = 4.5$ для каждого кластера. Известно, что количество точек не превышает 10000. Структура хранения информации в файле B аналогична структуре в файле А.

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

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

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

Гарантируется, что во всех кластерах количество точек различно.

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

Возможные данные одного из файлов проиллюстрированы графиком.

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

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/24985_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/24985_27B.txt