Задача #2595

(Д. Бахтиев) На складе с автоматической системой управления работают роботы, которые собирают грузы, расположенные на разных участках склада. Склад представляет собой прямоугольную сетку высотой $H$ и шириной $W$. Каждый робот может перемещаться только вдоль осей сетки (вверх, вниз, влево, вправо), поэтому для оценки расстояний между объектами используется манхэттенское расстояние.

Группа инженеров решила оптимизировать работу роботов, минимизировав общее время сбора грузов. Для этого необходимо определить координаты груза в каждом участке склада, для которой сумма расстояний от неё до всех грузов на участке будет минимальной. Эта точка называется центроидом. Робот, находящийся в центроиде, сможет быстрее собрать все грузы на своём участке.

Под расстоянием между двумя точками $A(x1,y1)$ и $B(x2,y2)$ понимается манхэттенское расстояние, которое вычисляется по формуле:

d(A,B)=|x2−x1|+|y2−y1|

В файле A хранятся данные о расположении грузов на двух участках склада, где каждый участок имеет размеры $H=10$ и $W=20$. В каждой строке записана информация о расположении одного груза: сначала координата $x$, затем координата $y$. Количество грузов в файле не превышает 1000.

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

Для каждого файла определите координаты центра каждого участка (центроида), а затем вычислите два числа:

• $Px$ — среднее арифметическое абсцисс центроидов участков,
• $Py$ — среднее арифметическое ординат центроидов участков.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $Px*1000$ затем целую часть абсолютного значения произведения $Py*1000$ для файла A; во второй строке — аналогичные данные для файла B.

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