UW Madison ICPC 2019-2020 training 1


2019-09-06 15:00 UTC

UW Madison ICPC 2019-2020 training 1


2019-09-13 15:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -44 days 2:11:40

Time elapsed


Time remaining


Problem A
Arctic Network


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.


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$).


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
2 4
0 100
0 300
0 600
150 750