TVTower

SRM 183 · 2004-02-11 · by brett1479

SRM 183 · 2004-02-11 · by brett1479 · Geometry

Show categories

Class Name: TVTower

Return Type: double

Method Name: minRadius

Arg Types: (vector<int>, vector<int>)

Problem Statement

Our problem is where to locate our TV station's broadcasting tower. We know the locations of the towns we should serve. Fortunately, we are located on the flat, flat prairie, so the only issue is where to locate the tower 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 elements of x and y give the coordinates of the i-th town. Create a class TVTower that contains a method minRadius that is given x and y, and returns the minimum broadcast radius that can reach all the towns. The tower's location is NOT restricted to 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 -1000 and 1000 inclusive.

Examples

{1, 0, -1, 0}
{0, 1, 0, -1}
Returns: 1.0

By symmetry we should locate the tower at the origin, which is in the center of the diamond formed by these 4 towns.

{3}
{299}
Returns: 0.0

Locate the tower right in the town.

{1000,1000,1000,1000,999}
{500,1000,-300,-989,-300}
Returns: 994.5

{5, 3, -4, 2}
{0, 4, 3, 2}
Returns: 4.743416490252569

{5,-3,-4}
{0,4,-3}
Returns: 5.0

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

Coding Area

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