1. Как на ЕГЭ (1). Программирование

 

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба.

Кластер звёзд — это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Центр кластера (центроид) — это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

 

Расстояние между двумя точками $A(x_1;y_1)$ и $B(x_2;y_2)$ вычисляется по формуле:

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

 

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

 

Даны два входных файла (файл A.txt и файл Б.txt).

В файле А хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата \(x\), затем координата \(y\) (в условных единицах). Известно, что количество звёзд не превышает 3500.

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

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

 

 

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

 

В ответе запиши четыре числа: в первой строке сначала целую часть произведения $P_x\times 100000$, затем целую часть произведения $P_y\times 100000$ для файла А, во второй строке — аналогичные данные для файла Б.

 

Ответ