3. Как на ЕГЭ (3). Программирование

В компьютерной игре учёному необходимо провести кластеризацию населённых пунктов двух больших районов на картах планет Альфа и Омега. Район (кластер) — это группа населённых пунктов, которые находятся внутри прямоугольника высотой \(H\) и шириной \(W\). 
Каждый населённый пункт обязательно принадлежит только одному району. Столица района (центроид) — это такой населённый пункт, сумма манхэттенских расстояний от которого до всех других населённых пунктов в кластере минимальна. Манхэттенское расстояние между двумя точками $A(x_1;y_1)$ и $B(x_2;y_2)$ вычисляется по формуле:

$d(A,B)=\left|x_1-x_2\right|+\left|y_1-y_2\right|$.

 

Даны два входных файла (файл A.txt и файл Б.txt).

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

В файле Б той же структуры хранятся данные о точках трёх кластеров. Количество точек в каждом кластере не превышает 11000. Возможные данные одного из файлов проиллюстрированы графиком.

 

 

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

 

В ответе запиши четыре числа: в первой строке сначала целую часть произведения $P_x\times 100000$, затем целую часть произведения $P_y\times 100000$ для файла А, во второй строке — аналогичные данные для файла Б.

 

Ответ