Connection Status:
Competition Arena > TVAntenna

TVAntenna

SRM 183 · 2004-02-11 · by dgoodman

SRM 183 · 2004-02-11 · by dgoodman · Geometry, Simple Search, Iteration
Class Name: TVAntenna
Return Type: double
Method Name: minRadius
Arg Types: (vector<int>, vector<int>)
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.

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
0)
{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.

1)
{3}
{99}
Returns: 0.0

Locate the tower right in the one town.

2)
{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
3)
{200,-200,4,8,23,-129}
{-200,200,138,-123,2,4}
Returns: 282.842712474619
4)
{-199,-199,-199,-199}
{-50,-100,-70,-69}
Returns: 25.0

Submissions are judged against all 24 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TVAntenna with a public method double minRadius(vector<int> x, vector<int> y) · 24 test cases · 2 s / 256 MB per case

Submitting as anonymous