How to solve python olympiad problem?

Question

Algorithms

The mission of radio engineering is to create a network of n antennas scattered across a vast desert, which can be represented as a two-dimensional plane. It will set the transmission radius of each antenna to the same non-negative real number r. The range of an antenna is defined as the set of all points whose distance does not exceed r. If the ranges of two antennas share a common point, these antennas can communicate directly. Also, if antennas A and B can communicate, as well as antennas B and C, then antennas A and C can also communicate through antenna B.
The radio engineer wants to connect the antennas into a network, that is, to make sure that every two antennas can communicate. Since he has limited costs for this mission, and larger radii require more money, he will choose the smallest possible radius r. Help him solve this problem!

Input
The input first line contains an integer n (1 ≤ n ≤ 1000), the number of antennas.
Each of the next n lines contains integers xi and yi (0 = xi , yi = 109 ), coordinates of the i-th antenna.
Output. Output the minimum radius. Your answer will be considered correct if its absolute or relative error does not exceed 10-6.
Input
2
1 1
2 2

Output
0.7071068

Answer 1

There are 2 approaches here - dichotomy (binary search) by answer, as Vasily Bannikov wrote : You are looking for the value of r by binary search. For each value, check if the graph of all antennas is connected through a depth-first traversal (an edge between two antennas if they see each other directly for a given r). Another option is through the Kruskal
spanning tree construction algorithm . Sort all possible edges in the graph (all distances between pairs of vertices). Then add edges to the initially empty graph in this order until it becomes connected (until you build a spanning tree). The last added edge will give r (half the length of the edge is the answer).

Answer 2

I would approach this: at what r can one or another pair of antennas communicate directly?
This will give you a finite set of N*(N-1)/2 r values ​​to include the answer.
And then you sort this set in ascending order, and for each r you check whether all antennas can communicate.
To do this, you take a set of antennas, which initially contains only antenna 1.
You iteratively look for all antennas that are not in this set, but that can communicate with antennas in the set, and add them to the set. And so on until you find at least one antenna that fits these conditions. (There's room for optimization here, think about it.)
If after that the size of the set is N, then it has all the antennas, and they can all communicate with each other.
If the size is less than N, then part of the antennas is unreachable, you need to take the next larger value of r.

Answer 3

Solution "In the forehead":
1. Set the initial r = The maximum distance between the two antennas.
2. by dividing by two, we are looking for the minimum allowable size at which all antennas remain connected
3. As soon as we have reached the required accuracy, we return the result.
The algorithm for checking antennas for connectivity is described in the problem.
More specifically - https://freelance.habr.com

Answer 4

In fact - for each antenna, find the distance to the nearest neighbor, and output the maximum of these distances, divided in half (I read this "If the ranges of two antennas have a common point, these antennas can directly interact" and whinnied, imagining how the antennas needed to interact, and a moron with a repeater jumped to this common point).
The second part of the task is generally simple as a bast shoe. So the main problem is for each antenna to find the distance to the nearest neighbor. Well, here, to speed up (if the antennas are really dofiga, 1000 from the task is not dofiga), you can use pre-selection on the grid (for 1000 antennas - grid 6 * 6) and post-selection if the deviation for any coordinate is greater than the current minimum distance. On average, this reduces the number of calculated distances by about a factor of three (999000 or 368000 distances - still a difference).