Изолированные точки

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

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

Изолированной точкой кластера назовём точку, в единичной окрестности от которой находится наименьшее количество точек кластера. Если таких точек несколько, то выбирается точка с наибольшей координатой y. Под расстоянием понимается расстояние Евклида между двумя точками 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.

Пример

Пояснение

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

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

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

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