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

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

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

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

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $P_{x}*1000$, затем целую часть абсолютного значения произведения $P_{y}*1000$ для файла А, во второй строке – аналогичные данные для файла B.

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

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

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

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