Миссия радиотехника состоит в создании сети из n антенн, разбросанных по обширной пустыне, которую можно представить в виде двумерной плоскости. Он установит радиус передачи каждой антенны равным одному и тому же неотрицательному вещественному числу r. Дальность действия антенны определяется как множество всех точек, расстояние до которых не превышает r. Если диапазоны двух антенн имеют общую точку, эти антенны могут напрямую взаимодействовать. Кроме того, если антенны A и B могут общаться, а также антенны B и C, то антенны A и C также могут общаться через антенну B.
Радиотехник хочет соединить антенны в сеть, то есть сделать так, чтобы каждые две антенны могли общаться. Поскольку ему ограничил расходы на эту миссию, а большие радиусы требуют больше денег, он выберет наименьший возможный радиус r. Помогите ему решить эту проблему!
Вход
Входная первая строка содержит целое число n (1 ≤ n ≤ 1000), количество антенн.
Каждая из следующих n строк содержит целые числа xi и yi (0 = xi , yi = 109 ), координаты i-й антенны.
Выход. Выведите минимальный радиус. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10-6.
Вход
2
1 1
2 2
Я бы подошёл так: при каком r сможет общаться напрямую та или иная пара антенн?
Это даст тебе конечное множество из N*(N-1)/2 значений r, в которое будет входить ответ.
А дальше сортируешь это множество по возрастанию, и для каждого r проверяешь, смогут ли общаться все антенны.
Для этого берешь множесто антенн, в котором сначала содержится только антенна 1.
Итеративно ищешь все антенны, которые не в этом множестве, но которые могут общаться с антеннами в множестве, и добавляешь их в множество. И так пока находишь хотя бы одну антенну, подходящую под эти условия. (Тут есть простор для оптимизаций, подумай.)
Если после этого размер множества равен N, то в нём все антенны, и все они могут общаться друг с другом.
Если размер меньше N, то часть антенн недостижима, нужно брать следующее большее значение r.
