Задача #2610

(Л. Шастин) Популярная компания по доставке продуктов «Быстрокат» расширяется и хочет открыть новые филиалы в двух густонаселенных районах города. Для открытия отдела логистам необходимо выбрать самую подходящую геолокацию для оптимизации организации процессов по координации и доставке товаров, для чего им нужно проанализировать множество жилых единиц (геопозиций). Каждый район состоит из нескольких микрорайонов, включающих в себя некоторое количество геопозиций. Известно, что каждый микрорайон характеризуется тем, что любая из его геопозиций удалена от любой геопозиции из других микрорайонов хотя бы на $R$ у.е. (условных единиц). Для анализа данных используется предоставленный набор вещественных точек (геопозиций), размещенных на декартовой оси координат. Они характеризуют все геопозиции конкретного района, который представляет собой квадрат размером $10$ у.е. (условных единиц). С целью определить оптимальную геолокацию для открытия филиала логисты вычисляют медоид (райцентр) каждого микрорайона, который определяется как такая геопозиция внутри одного микрорайона, суммарное расстояние от которой до всех других геопозиций этого же микрорайона минимально. Затем специалисты определяют конечный медоид, опираясь на данные о расположении ранее найденных медоидов, – такую геопозицию, суммарное расстояние от которой до всех медоидов минимально. Именно в этой геопозиции и будет затем открыт новый филиал. При проведении расчетов также исключаются аномальные геопозиции, случайно попавшие в представленный набор данных. Они определяются как точки, расстояние от которых до любой другой точки в наборе данных превышает $K$ у.е. (условных единиц). Метрикой расстояния между двумя геопозициями (точками) $A(x1,y1)$ и $B(x2,y2)$ на плоскости является формула Евклида: $d(A,B)=$ $\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$.

В файле A хранятся данные обо всех геопозициях первого района. В первой строке записаны значения $R$ и $K$ для этого района. В каждой из следующих строк записана информация о расположении в районе одной геопозиции: сначала координата $x$, затем координата $y$. Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество геопозиций не превышает 2000. В файле Б хранятся данные обо всех геопозициях второго района. В первой строке записаны значения $R$ и $K$ для этого района. Известно, что количество геопозиций не превышает 30 000. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите геопозицию, в которой будет открыт филиал. В ответе запишите четыре числа: в первой строке сначала целую часть произведения координаты $x$ этой геопозиции на $10000$, затем целую часть произведения координаты $y$ этой геопозиции на $10000$ для файла А, во второй строке – аналогичные данные для файла Б.

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