Задача #2907

(М. Попков) На далёкой засекреченной космической станции, затерянной в пустынных уголках вселенной, гениальный, но сумасшедший учёный доктор Астрономикс проводит эксперименты с кластеризацией звёздных карт. Он утверждает, что можно открыть портал в параллельное измерение. Для проверки своей гипотезы он анализирует группы звёзд, лежащие внутри прямоугольника – кластеры. Каждая звезда обязательно принадлежит только одному из кластеров.

Для его экспериментов необходимо определить истинный центр каждого кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

Под расстоянием понимается расстояние Чебышева между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ на плоскости, которое вычисляется по формуле: $d(A,B)=max(|x_2-x_1|,|y_2-y_1|)$.

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

В файле B хранятся данные о звёздах четырёх кластеров. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.

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

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

По словам учёного, правильный результат может помочь настроить телепорт к звёздному измерению… или взорвать станцию, если вы ошибётесь!

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

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

Для выполнения задания используйте данные из прилагаемого файла.