Центр центров

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на плоской карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на карте. Каждая звезда обязательно принадлежит только одному из кластеров. Между любой парой звёзд кластера существует маршрут, проходящий через звёзды, отдалённые друг от друга не более чем на единицу. Каждый кластер содержит не менее 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), суммарное расстояние от которой до всех центров кластеров будет минимальным. Если таковых решений несколько, то следует выбрать точку с наименьшим значением P_x.

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

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

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

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

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

Пример

Пояснение

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

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

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

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