Arctic Network#10203
The Ministry of National Defense (MND) plans to connect several northern outposts into a single wireless network. Two different communication technologies must be used to build the network: each outpost will be equipped with a radio transceiver, and some of them will additionally have a satellite channel.
Any two outposts equipped with a satellite channel can communicate with each other via satellite, regardless of the distance between them. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed , which depends on the power of the transceivers. The higher the power, the larger the value of , but the cost of the equipment also increases. For economic and maintenance reasons, all transceivers must be identical, meaning that the value of must be the same for all pairs of outposts.
You must determine the minimum value of required so that communication is possible between any two outposts — either directly or indirectly (through other outposts).
The first line contains the number of test cases . The first line of each test case contains the number of satellite channels s~(1 \le s \le 100) and the number of outposts p~(s < p \le 500). Each of the next lines contains the coordinates of an outpost in kilometers (integers from to ).
For each test case, print the minimum value of required to connect all outposts into a single network. Print the result with exactly two digits after the decimal point.
Пример 1