Задача #2708

(М. Попков) Снежная королева решила провести кластеризацию жителей своей страны по деревням и узнать, в каком месте каждой деревни расположить место спортивных мероприятий. Каждый дом имеет свои координаты на плоскости, и необходимо определить центры кластеров, чтобы оптимально организовать зимние мероприятия.

В файле A содержится информация о расположении домов в двух деревнях. В каждой строке записаны координаты одного дома: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество домов не превышает 1000.

В файле B содержится информация о домах трех деревней. Количество домов не превышает 10 000. Структура хранения информации аналогична файлу A.

Лучшее место для спортивных развлечений - центроид, – это место около одного дома деревни, сумма расстояний от которой до всех остальных звезд кластера минимальна. Расстояние между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле:

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

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

В ответе запишите четыре числа: в первой строке сначала целая часть произведения $P_x\times 10000$, затем целая часть произведения $P_y\times 10000$ для файла A, во второй строке – аналогичные данные для файла B.