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 on 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.
Given the (x, y) coordinates of each outpost, and informations about which outposts
have a satellite channel, show an algorithm to determine the minimum D required for
the transceivers and analyse the running time. There must be at least one communication
path between every pair of outpost. (You can test your algorithm with an
automatic grader at UVa 10369.)