Problem C
Arctic Network
![/problems/arcticnetwork/file/statement/en/img-0001.jpg](/problems/arcticnetwork/file/statement/en/img-0001.jpg)
The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.
Any two outposts with a satellite channel can communicate via the satellite, regardless of their location. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed $D$, which depends of the power of the transceivers. Higher power yields higher $D$ but costs more. Due to purchasing and maintenance considerations, the transceivers at the outposts must be identical; that is, the value of $D$ is the same for every pair of outposts.
Your job is to determine the minimum $D$ required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts.
Input
The first line of input contains $N$, the number of test cases. The first line of each test case contains $1 \le S \le 100$, the number of satellite channels, and $S < P \le 500$, the number of outposts. $P$ lines follow, giving the ($x,y$) coordinates of each outpost in km (coordinates are integers between $0$ and $10\, 000$).
Output
For each case, output should consist of a single line giving the minimum $D$ required to connect the network. Output should be specified to $2$ decimal points.
Sample Input 1 | Sample Output 1 |
---|---|
1 2 4 0 100 0 300 0 600 150 750 |
212.13 |