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

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Антицентр кластера – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера максимальна. Для каждого кластера гарантируется единственность его антицентра. Расстояние между двумя точками на плоскости $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 хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

В файле B имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

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

Для файла B определите координаты антицентра каждого кластера, затем найдите два числа: $Q_1$ - абсциссу антицентра кластера, наиболее отдалённого от начала координат, и $Q_2$ - ординату антицентра кластера, ближайшего к началу координат.

Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке - сначала абсолютную величину целой части произведения $P_x*10000$, затем абсолютную величину целой части произведения $P_y*10000$; во второй строке - начала абсолютную величину целой части произведения $Q_1*10000$, затем абсолютную величину целой части произведения $Q_2*10000$.

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

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

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

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