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

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

В файле A хранятся координаты звёзд, расположенных в 2 кластерах, размеры кластеров $H=5$, $W=4$, не более 1000 точек.

В файле B хранятся координаты звёзд в 3 кластерах, размеры кластеров $H=4$, $W=5$, не более 10000 точек.

Каждая строка файлов A и B содержит два числа — координаты звезды: сначала по оси x, затем по оси $y$.

Для каждого файла определите координаты центра и антицентра каждого кластера, затем вычислите два числа: $P_x$​ – среднее арифметическое абсцисс центров кластеров, и $S_y$​ – среднее арифметическое ординат антицентров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $P_x​*10000$, затем целую часть абсолютного значения произведения $S_y*10000$ для файла А, во второй строке – аналогичные данные для файла B.

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

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

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

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