Миссия радиотехника состоит в создании сети из 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
Тут есть 2 подхода - дихотомия (бинарный поиск) по ответу, как написал Василий Банников: Вы бинарным поиском ищите значение r. Для каждого значения проверяете, а связен ли граф всех антен через обход в глубину (ребро межу двумя антеннами, если они видят друг друга напрямую для данного r).
Другой вариант - через алгоритм построения остовного дерева Краскала. Сортируете все возможные ребра в графе (все расстояния между парами вершин). Потом добавляйте в изначально пустой граф ребра в этом порядке, пока он не станет связен (пока не построите остовное дерево). Последнее добавленное ребро и будет задавать r (половина длины ребра - ответ).
Я бы подошёл так: при каком r сможет общаться напрямую та или иная пара антенн?
Это даст тебе конечное множество из N*(N-1)/2 значений r, в которое будет входить ответ.
А дальше сортируешь это множество по возрастанию, и для каждого r проверяешь, смогут ли общаться все антенны.
Для этого берешь множесто антенн, в котором сначала содержится только антенна 1.
Итеративно ищешь все антенны, которые не в этом множестве, но которые могут общаться с антеннами в множестве, и добавляешь их в множество. И так пока находишь хотя бы одну антенну, подходящую под эти условия. (Тут есть простор для оптимизаций, подумай.)
Если после этого размер множества равен N, то в нём все антенны, и все они могут общаться друг с другом.
Если размер меньше N, то часть антенн недостижима, нужно брать следующее большее значение r.
Вариант решения "В лоб":
1. Задаём начальное r = Максимальное расстояние между двумя антеннами.
2. делением на два ищем минимально допустимый размер, при котором все антенны остаются соединены
3. Как только достигли требуемой точности - отдаём результат.
Алгоритм для проверки антенн на соединённость описан в задаче.
По сути - для каждой антенны найти расстояние до ближайшего соседа, и вывести максимальное из этих расстояний, делённое пополам (вот читал это "Если диапазоны двух антенн имеют общую точку, эти антенны могут напрямую взаимодействовать" и ржал, представляя, как антеннам потребовалось взаимодействовать, и в эту общую точку поскакал придурок с репитером).
Вторая часть задания вообще проста как лапоть. Так что основная проблема - для каждой антенны найти расстояние до ближайшего соседа. Ну тут для ускорения (если антенн реально дофига, 1000 из задания - это не дофига) можно использовать пред-отбор по сетке (для 1000 антенн - сетка 6*6) и пост-отбор если отклонение по любой координате больше текущего минимального расстояния. В среднем это снижает количество считаемых расстояний где-то втрое (999000 или 368000 расстояний - всё же разница).
Средний
