Антицентр

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

Известно, что любые две звезды, не принадлежащие одному кластеру или аномалии, отдалены друг от друга более чем на единицу.

Антицентр кластера – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера максимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x₁,y₁) и B(x₂,y₂) на плоскости, которое вычисляется по формуле:

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

По заданным координатам звёзд необходимо найти антицентры кластеров и вычислить следующие два параметра:

• P_x – среднее арифметическое абсцисс антицентров кластеров
• P_y – среднее арифметическое ординат антицентров кластеров

Входные данные

Входной файл INPUT.TXT содержит не более 1000 строк. В каждой строке записаны два вещественных числа x_i, y_i – координаты звезды.

Гарантируется, что на представленной карте звёздного неба присутствует от 2 до 10 кластеров и при этом антицентр каждого кластера определяется однозначно.

Выходные данные

В выходной файл OUTPUT.TXT выведите два целых числа: целую часть абсолютного значения 10 000 × P_x и целую часть абсолютного значения 10 000 × P_y.

Пример

Пояснение

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

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

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]