Задание №27

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

При этом используется следующее определение архипелага и одиночного острова: острова принадлежат одному и тому же архипелагу, если между ними существует цепочка соседних островов (то есть, для любой пары островов A и B в архипелаге можно найти последовательность А = Р₁, Р₂, ..., Р_k = B, где расстояние между соседними островами Р_i и P_i+1 меньше 1). Архипелагом считается только такое объединение островов, в котором общее количество островов не менее 20. Если какая-либо группа островов, связанная по вышеописанному принципу, содержит менее 20 островов, она не рассматривается как архипелаг, а все входящие в неё острова считаются одиночными и не учитываются в дальнейшем анализе.

Антицентроидом архипелага называется такой остров, принадлежащий архипелагу, для которого сумма расстояний до всех остальных островов этого архипелага максимальна. При условии, что одиночные острова при расчётах игнорируются, требуется определить координаты М_х и М_у антицентроида с наименьший суммой расстояний до других островов своего архипелага.

Входные данные задаются в двух файлах: файл A и файл B. В каждой строке файлов содержатся координаты островов: сначала по оси x, затем по оси y. Количество островов не превышает 1000 для файла A и не превышает 11 000 для файла B.

В ответе запишите четыре числа: в первой строке – целые части абсолютных значений произведений М_х × 10 000 и М_у × 10 000 для файла A. Во второй строке – целые части абсолютных значений произведений М_х × 10 000 и М_у × 10 000 для файла B.

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