Задача #2934

(Д. Бахтиев) Учёный решил провести кластеризацию множества звёзд по их расположению на карте звёздного неба. Каждая звезда задаётся своими координатами $(x,y)$. Две звезды считаются соседними, если расстояние между ними по формуле Евклида

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

строго меньше 1 условной единицы.

При этом используется следующее определение кластера и аномалии: звезды принадлежат одному и тому же кластеру, если между ними существует цепочка соседних звёзд (то есть, для любой пары звёзд $A$ и $B$ в кластере можно найти последовательность

$A=P_1,P_2,\dots ,P_k=B,$

где расстояние между соседними звёздами $P_i$ и $P_{i+1}$ меньше 1). При этом кластером считается только такое объединение звёзд, в котором общее число точек не менее 20. Если какая-либо группа звёзд, связанная по вышеописанному принципу, содержит менее 20 точек, она не рассматривается как кластер, а все входящие в неё звёзды считаются аномалиями.
Входные данные задаются в двух файлах: файл A и файл B. В каждой строке файлов содержатся координаты звёзд: сначала по оси $x$, затем по оси $y$.
При условии, что аномалии при расчётах игнорируются, требуется определить координаты центроида самого маленького (по числу звёзд) кластера. Центроид кластера определяется как звезда, принадлежащая кластеру, для которой сумма расстояний до всех остальных звёзд этого кластера минимальна. Гарантируется, что такой кластер определяется однозначно. В ответе запишите четыре числа: в первой строке для файла A результаты произведений $C_x*10000$ и $C_y*10000$, где $C_x$ и $C_y$ — координаты центроида кластера по осям $x$ и $y$ соответственно, а во второй строке аналогичные данные для файла B.