Задача #2968

(М. Попков) Команда астронавтов на борту исследовательского корабля “Интерстеллар-6” отправилась в глубокий космос для картографирования далёких звёздных систем. Их миссия – провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба и найти края кластеров, до которых можно добраться с помощью межзвездных прыжков. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника. Каждая звезда обязательно принадлежит только одному из кластеров.

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

Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ на плоскости, которое вычисляется по формуле: $d(A,B)=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$.

Нано-кластером назовём кластер, содержащий наименьшее количество звезд. В дальнейших расчётах нано-кластер учитывать не нужно. Значимыми назовем остальные кластеры.

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

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

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

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

Эти вычисления помогут экипажу “Интерстеллара-6” безопасно выйти за пределы известных звёздных маршрутов и открыть новые пути в неизведанную часть галактики. Но будьте осторожны — ошибка может привести корабль в ловушку гравитации чёрной дыры!

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

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

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