TopCoder problem "TVAntenna" used in SRM 183 (Division II Level Three)

Problem Statement

    Our problem is where to locate our TV station's broadcasting antenna. We know the locations of the towns we should serve. We must place the antenna at a point whose coordinates are both integers. Fortunately, we are located on the flat, flat prairie, so the only remaining issue is to locate the antenna to minimize the broadcast radius that includes all the towns.

We have int[] x and int[] y giving the locations of the towns; the i-th element of x and y gives the coordinates of the i-th town. Create a class TVAntenna that contains a method minRadius that is given x and y, and returns the minimum broadcast radius that can reach all the towns from a location with integer coordinates.



Parameters:int[], int[]
Method signature:double minRadius(int[] x, int[] y)
(be sure your method is public)


-If the return has either a relative or absolute error less than 1.0E-9 it is acceptable.


-x will contain between 1 and 50 elements inclusive.
-y will contain the same number of elements as x.
-Each element in x and y will be between -200 and 200 inclusive.


Returns: 1.4142135623730951
The towns are located at (2,0), (0,1), (0,-1) and (1,1). The obvious location for the antenna is at (1,0). From there the distances to the four towns are 1, sqrt(2), sqrt(2) and 1, so a broadcast radius of sqrt(2) will reach all four towns. The next best location for the antenna at integer coordinates would be at (1,1) but then one of the towns would be sqrt(5) away from the antenna.
Returns: 0.0
Locate the tower right in the one town.

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

Geometry, Simple Search, Iteration