TopCoder Statistics - Problem Statement

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.

Definition

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

Notes

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

Constraints

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.

Examples

{2,0,0,1}

{0,1,-1,1}

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.
{3}

{99}

Returns: 0.0

Locate the tower right in the one town.
{200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200}

{200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200,200}

Returns: 0.0
{200,-200,4,8,23,-129}

{-200,200,138,-123,2,4}

Returns: 282.842712474619
{-199,-199,-199,-199}

{-50,-100,-70,-69}

Returns: 25.0
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}

Returns: 34.655446902326915
{-89,-89,-89}

{-89,-90,-91}

Returns: 1.0
{0,1}

{0,1}

Returns: 1.0
{5,9,2,-4}

{3,33,21,-5}

Returns: 20.248456731316587
{12,13,14,15,16,17,18}

{200,-200,200,-200,200,-200,200}

Returns: 200.02249873451737
{23,65,91,12,14,39}

{43,44,29,35,36,33}

Returns: 40.0
{23,65,91,12,14,39}

{23,65,91,12,14,39}

Returns: 55.86591089385369
{23,65,91,12,14,39}

{39,23,65,91,12,14}

Returns: 49.8196748283246
{5,9,2,-4}

{-4,5,9,2}

Returns: 7.0710678118654755
{0,33}

{0,44}

Returns: 27.65863337187866
{-200}

{-200}

Returns: 0.0
{ -200, 200 }

{ -200, 200 }

Returns: 282.842712474619
{ 2, 0, 0, 1, 50 }

{ 0, 1, -1, 1, 50 }

Returns: 36.069377593742864
{ 200 }

{ 200 }

Returns: 0.0
{ 0, 1, 2, 13 }

{ 0, 0, 0, 0 }

Returns: 7.0
{ 0, 7, 7 }

{ 6, 0, 11 }

Returns: 6.082762530298219
{ 24, -33, -5, -47, 20, -35, -17, -19, -19, 18, -28, -29, 28, 16, 29, 6, 19, -34, -44, 10, 14, -31, -21, -17, -33, -3, 18, -25, 5, 4, 4, -49, 21, -31, -45, -36, 17, 20, 27, -32, -39, 1, 22, -41, 20, -27, 15, -39, -11, -27 }

{ -15, -17, 27, -31, -36, -35, -12, 22, -13, 3, 18, -24, -33, -50, -50, 23, -6, -28, 2, -19, -6, -41, -31, 9, 15, -27, 10, -49, -13, -12, -29, -26, 21, 1, 26, -45, 16, -16, -20, 5, -11, -32, -17, -42, -32, -17, -17, 12, -43, -45 }

Returns: 53.03772242470448
{ 0, 100, 101 }

{ 0, 0, 0 }

Returns: 51.0
{ -100, 0, 100 }

{ 0, 100, 0 }

Returns: 100.0

Statistics

Problem Statement for "TVAntenna"

Problem Statement

Definition

Notes

Constraints

Examples