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

Компания «Энергосеть» занимается оптимизацией энергоснабжения в нескольких регионах. Для этого нужно определить местоположение главных трансформаторных узлов, которые обеспечат минимальные потери при распределении энергии. В каждом регионе имеются несколько подрегионов, каждый из которых характеризуется тем, что расстояние от любой точки в подрегионе до точки из другого подрегиона не менее $R$ условных единиц.

Необходимо определить место для трансформаторного узла, которое находится за два шага: сначала для каждого подрегиона нужно найти его центр нагрузки — такую точку в подрегионе, от которой суммарное расстояние до всех остальных точек подрегиона минимально. Затем, учитывая данные о центрах нагрузки всех подрегионов, найти центральный трансформаторный узел — такая точка в регионе, от которой суммарное расстояние до всех центров нагрузки минимально. Если подходящих точек несколько, выбирается та, у которой абсцисса наименьшая. Расстояние между двумя точками $(x_1, y_1)$ и $(x_2, y_2)$ на плоскости вычисляется по формуле Евклида:

$d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

Файл A содержит данные о точках двух подрегионов. Файл B содержат данные о точках трёх подрегионов. В первой строке каждого файла записано значения $R$. В каждой из следующих строк записаны координаты $x$ и $y$ очередной точки. Количество точек в файле A не превышает 1000, в B не превышает 10000.

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

В ответе укажите четыре целых числа: в первой строке - ближайшие целые числа значений произведения координаты $x$ узла на 10000 и координаты $y$ узла на 10000 для региона А; во второй строке - аналогичные данные для региона В.

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

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