Центро-удалённые точки

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

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

Центр кластера – это одна из точек, сумма расстояний от которой до всех остальных точек кластера минимальна.

Цетро-удаленная точка – это такая точка кластера, расстояние от которой до центра кластера превосходит среднее арифметическое расстояний от центра до всех точек этого кластера, включая сам центр кластера.

Под расстоянием понимается расстояние Евклида между двумя точками A(x₁,y₁) и B(x₂,y₂) на плоскости, которое вычисляется по формуле:

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

По заданным координатам звёзд для каждого кластера найдите количество центро-удаленных точек.

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

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

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

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

В выходной файл OUTPUT.TXT выведите два целых числа: K_min и K_max – минимальное и максимальное количество центро-удаленных точек среди всех кластеров.

Пример

Пояснение

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

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

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

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