Statistics

Problem Statement for "TVTower"

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.

Definition

Class:
TVTower
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 -1000 and 1000 inclusive.

Examples

  1. {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.

  2. {3}

    {299}

    Returns: 0.0

    Locate the tower right in the town.

  3. {1000,1000,1000,1000,999}

    {500,1000,-300,-989,-300}

    Returns: 994.5

  4. {5, 3, -4, 2}

    {0, 4, 3, 2}

    Returns: 4.743416490252569

  5. {5,-3,-4}

    {0,4,-3}

    Returns: 5.0

  6. {52,-28,-38}

    {7,47,-23}

    Returns: 50.0

  7. {-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000}

    {-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000}

    Returns: 0.0

  8. {-1000,-1000,100,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000}

    {-1000,500,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000,-1000}

    Returns: 930.0537618869137

  9. {1,11}

    {1,9}

    Returns: 6.4031242374328485

  10. {1,0,11}

    {1,2,9}

    Returns: 6.519202405202649

  11. {1,0,11}

    {1,3,9}

    Returns: 6.4031242374328485

  12. {9,3,-12,-17}

    {3,-12,-17,9}

    Returns: 15.857491600939305

  13. {-976,435,812,-666,234,845,123,-123}

    {772,-976,435,812,-666,234,845,123}

    Returns: 1126.3615357770154

  14. {-1000,0,1000,921}

    {1000,0,-1000,543}

    Returns: 1414.213562373095

  15. {3,121,5,92}

    {7,243,11,185}

    Returns: 131.9280106724876

  16. { 0, 7, 0 }

    { 0, 5, 10 }

    Returns: 5.285714285714286

  17. { 0, 0, -5, 5 }

    { -3, 7, 0, 0 }

    Returns: 5.285714285714286

  18. { 0, 500, 1000 }

    { 0, 866, 0 }

    Returns: 577.3418013856813

  19. { 0, -5, 5, 1 }

    { 5, -5, -5, 1 }

    Returns: 6.25

  20. { -1000, 0, 1000, -500, 500, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900 }

    { -1000, 732, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000 }

    Returns: 1154.6836027713628

  21. { 0, 3, 6 }

    { 0, 10, 0 }

    Returns: 5.45

  22. { 0, 3, 6 }

    { 0, 4, 0 }

    Returns: 3.125

  23. { -5, 1, 2, 3, 4 }

    { 10, 5, 3, 5, 7 }

    Returns: 5.0

  24. { 690, 633, -649, -975, 409, -678, 624, -976, -460, -102, -983, 120, 202, 75, 826, -339, -709, 620, 204, -666, 718, -299, 290, 383, 634, 235, 571, -651, -984, -99, 448, 263, -466, 356, -155, 500, 678, -531, 81, -783, -76, 98, -106, -875, 730, -723, -656, -980, 454, 548 }

    { 913, 171, 807, 202, -446, 440, 994, 682, 789, 567, -418, 236, -170, 116, -851, 232, -828, 827, 258, 253, 602, 740, 908, -505, 865, 638, -671, 766, 215, 784, -129, -316, -46, -323, 886, 65, 674, 880, -254, 462, 446, 329, -746, 833, -999, -597, -378, -826, 788, 880 }

    Returns: 1227.4930366680005

  25. { 0, 1, -1 }

    { 6, 0, 0 }

    Returns: 3.0833333333333335

  26. { 0, 10, -1 }

    { 10, 0, -1 }

    Returns: 7.188918942063233

  27. { 0, 0, 7, -3 }

    { 5, 5, 0, 0 }

    Returns: 5.015974481593781

  28. { 0, 0, 8 }

    { 5, -5, 0 }

    Returns: 5.5625

  29. { 1, 0, -1 }

    { 0, 2, 0 }

    Returns: 1.25

  30. { -1000, 0, 1000 }

    { -866, 866, -866 }

    Returns: 1154.6836027713628

  31. { 0, 0, 7, 3 }

    { 5, -5, 0, 0 }

    Returns: 5.285714285714286

  32. { 0, 1000, 500 }

    { 0, 0, 866 }

    Returns: 577.3418013856813

  33. { 0, 2, 1 }

    { 0, 0, 2 }

    Returns: 1.25

  34. { 0, 5, 10 }

    { 0, 10, 0 }

    Returns: 6.25

  35. { 0, 4, 2 }

    { 0, 0, 3 }

    Returns: 2.166666666666667

  36. { 1, 2 }

    { 1, 2 }

    Returns: 0.7071067811865476

  37. { 0, 6, 3 }

    { 0, 0, 4 }

    Returns: 3.125

  38. { 0, 10, 5 }

    { 0, 0, 8 }

    Returns: 5.5625

  39. { 0, 1, 2 }

    { 0, 0, 0 }

    Returns: 1.0

  40. { 0, 5, 10 }

    { 0, 8, 0 }

    Returns: 5.5625

  41. { -10, 10, 0 }

    { 10, 10, -15 }

    Returns: 14.5

  42. { 1, 0 }

    { 1, 0 }

    Returns: 0.7071067811865476

  43. { 4, 4, 0, 0 }

    { 4, 0, 0, 4 }

    Returns: 2.8284271247461903

  44. { -500, 500, 0, 0 }

    { 500, 500, -366, 640 }

    Returns: 577.3418013856814

  45. { 0, 1 }

    { 0, 1 }

    Returns: 0.7071067811865476

  46. { 933, 743, 262, 529, 700, 508, 752, 256, 256, 119, 711, 351, 843, 705, 108, 393, 330, 366, 169, 932, 917, 847, 972, 868, 980, 223, 549, 592, 164, 169, 551, 427, 190, 624, 635, 920, 944, 310, 862, 484, 363, 301, 710, 236, 876, 431, 929, 397, 675, 491 }

    { 190, 344, 134, 425, 629, 30, 727, 126, 743, 334, 104, 760, 749, 620, 256, 932, 572, 613, 490, 509, 119, 405, 695, 49, 327, 719, 497, 824, 596, 649, 356, 184, 93, 245, 7, 306, 509, 754, 352, 665, 783, 738, 801, 690, 330, 337, 195, 656, 963, 11 }

    Returns: 517.1671916738641

  47. { 0, 0, 15, 15 }

    { 0, 20, 8, 12 }

    Returns: 10.885311203635842

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: