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

На складе с автоматической системой управления работают роботы, которые собирают грузы, расположенные на разных участках склада. Склад представляет собой прямоугольную сетку высотой $H$ и шириной $W$. Каждый робот может перемещаться только вдоль осей сетки (вверх, вниз, влево, вправо), поэтому для оценки расстояний между объектами используется манхэттенское расстояние. Под расстоянием между двумя точками $A(x1, y1)$ и $B(x2, y2)$ понимается манхэттенское расстояние, которое вычисляется по формуле:

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

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

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

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

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

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

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

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

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

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