Расстояния между кластерами

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

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

Назовем минимальным расстоянием между двумя кластерами минимальное расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая – другому.

Назовем максимальным расстоянием между двумя кластерами максимальное расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая – другому.

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

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

По заданным координатам звёзд найдите D_min и D_max – минимальное и максимальное расстояния между кластерами.

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

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

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

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

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

Пример

Пояснение

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

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

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

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