Statistics

Problem Statement for "Travel"

Problem Statement

A traveling salesman has recently decided to go international and sell his wares around the globe. He has done in depth research and has come up with a list of cities which he thinks will provide the best market for his goods. In planning his trip, the salesman wants to minimize the total distance he has to travel because he does not particularly like traveling (which is unfortunate for him, as he is a traveling salesman) and furthermore, he figures the less distance he has to travel, the cheaper his trip will be. However, this salesman is not particularily good at math, and so you must write a computer program to help him find his way in the least distance.

You will be given a set of cities defined by their longitudes and latitudes. In addition, you will be given the radius of the planet that this traveling salesman resides on. Assume that there are direct flights, both ways, between every pair of cities that the salesman wants to visit, and that the flights follow the shortest path possible (over the surface of the planet). In addition, the first element of the input String[] will be the city in which the salesman lives, and thus his trip must start and end at this city.

Each city is defined by two numbers, a latitude and a longitude. The latitude is the number of degrees above the equator, with 90 being the north pole, and -90 being the south pole. The longitude is the number of degrees east or west of some arbitrary, predefined point. Thus, 90 degrees east is one quarter of the way around the globe in the eastern direction.

If the result is not an integer, round it to the nearest integer (.5 rounds up)

Definition

Class:
Travel
Method:
shortest
Parameters:
String[], int
Returns:
int
Method signature:
int shortest(String[] cities, int radius)
(be sure your method is public)

Notes

  • Assume the planet is a perfect sphere.
  • To find the cartesion coordinates of a city, assuming the center of the planet is at (0,0,0), use the following formulas:x = r*cos(latitude)*cos(longitude)y = r*cos(latitude)*sin(longitude)z = r*sin(latitude)

Constraints

  • cities contains between 2 and 9 elements, inclusive.
  • Each element of cities represents a unique point on the globe.
  • Each element of cities is formatted as " " where is an integer in the range -90 to 90, inclusive, and is an integer in the range -180 to 180, inclusive.
  • radius is an integer between 1 and 1,000, inclusive.
  • to avoid rounding errors, the shortest path, prior to rounding, will not be within 0.001 of +0.5 for any integer .

Examples

  1. {"26 -126","-52 53","-20 -89","-61 -92","0 -78","-22 -1","-83 87"}

    351

    Returns: 2142

  2. {"90 0","0 0","-90 0","0 180","0 90","0 -90"}

    1000

    Returns: 9425

  3. {"0 0","0 1"}

    1000

    Returns: 35

    The two cities are located one degree apart at the same latitude

  4. {"0 0","0 1","0 -1","-1 0","1 0","-1 -1","1 1","1 -1","-1 1"}

    1

    Returns: 0

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

    10

    Returns: 2

  6. {"40 -82","-27 -59","-40 48" ,"26 -12","-31 -37","-30 42" ,"-36 -23","-26 71","-19 83","8 63"}

    698

    Returns: 4505

  7. {"-32 28","-19 115","-81 -63","-6 -179","-56 68","50 -59","-60 7","89 83"}

    849

    Returns: 6893

  8. {"-71 -74","18 52","-87 176"}

    528

    Returns: 2287

  9. {"-35 108","-12 -6","-13 137","-31 132"}

    453

    Returns: 2180

  10. {"64 -113","-5 122","84 -133","-31 38"}

    490

    Returns: 2898

  11. {"2 -2","-44 -18","-63 -160","-40 -12","67 168","-7 174","42 -124","84 -132","4 -2"}

    130

    Returns: 925

  12. {"-45 -86","-45 79","13 48","-60 -127","-66 -121","74 117","15 -3","76 3"}

    15

    Returns: 110

  13. {"14 -108","-27 49","63 0","34 -113","90 -171","20 102"}

    931

    Returns: 6492

  14. {"-25 169","74 172","52 -84","54 125","63 -165","65 -98","56 157","-7 129"}

    442

    Returns: 2444

  15. {"26 88","-2 -148","63 124","-4 72","-63 34","-64 -40","55 -59"}

    957

    Returns: 7066

  16. {"52 -150","-16 -166","-88 -166","58 -157","58 147","-32 41"}

    125

    Returns: 790

  17. {"1 -69","-44 83","-59 -79","-64 10"}

    998

    Returns: 4647

  18. {"-73 97","61 -53","16 -62"}

    647

    Returns: 3735

  19. {"-63 -54","-9 -36","-45 84","-49 -22","28 12","7 -50","-20 -7","-72 -39","-3 -90"}

    253

    Returns: 1780

  20. {"54 96","10 -165","8 0","-67 -90"}

    48

    Returns: 306

  21. {"9 67","65 50","-12 130","39 156","-5 37","-45 107","-38 120"}

    636

    Returns: 3551

  22. {"28 -91","22 122","77 -77"}

    346

    Returns: 1513

  23. {"62 -172","0 24","51 25","-49 83","27 -79","80 176","-24 -104","-73 51"}

    853

    Returns: 6269

  24. {"-33 122","-79 5","-47 -12","-70 22"}

    376

    Returns: 1220

  25. {"-30 10","-73 109","-46 178","35 55","74 -54","-71 -21","-21 132"}

    370

    Returns: 2763

  26. {"90 159","-5 -132","-2 -152","9 158","19 165"}

    761

    Returns: 3311

  27. {"-70 19","-46 -43","-9 -89","36 -75","-24 143","-25 40"}

    99

    Returns: 728

  28. {"-2 -53","-5 132"}

    89

    Returns: 532

  29. {"-32 161","6 -6","-15 24","84 -26"}

    718

    Returns: 4514

  30. {"5 -96","-2 -46","-55 -148","-53 28"}

    15

    Returns: 72

  31. {"53 169","-57 -163","68 59","-66 -23","-84 -152","-28 -134","-36 -13"}

    59

    Returns: 393

  32. {"-84 58","0 134","-32 -167","-29 -15"}

    962

    Returns: 5447

  33. {"21 -136","65 -122","-63 88","-62 -103","12 -146","-22 -123","-63 -70","72 153"}

    180

    Returns: 1195

  34. {"69 -84","12 137","44 -19","66 0","44 168","2 -135","-65 171","-7 138","20 -179"}

    777

    Returns: 5940

  35. {"-24 -133","-75 -4","-40 -170","24 65","-49 -168","-36 -48","-45 -142"}

    301

    Returns: 2129

  36. {"67 28","33 133","-33 4"}

    137

    Returns: 729

  37. {"31 161","25 -31","-1 9"}

    751

    Returns: 4056

  38. {"-60 68","-52 128","90 -99","8 -140","-33 175","-83 5","-37 -32","-15 122"}

    778

    Returns: 6312

  39. {"53 115","-62 -112","16 -159","53 65","45 -133","-8 142","72 165","74 18","-30 -81"}

    127

    Returns: 991

  40. {"64 146","41 -44","37 83","-20 -104"}

    415

    Returns: 2411

  41. {"-34 -91","74 40","-49 -44","-39 -177"}

    977

    Returns: 6480

  42. {"83 117","49 24","-72 -27","16 14","79 -158","-73 54","79 -47","18 -148","-70 -1"}

    371

    Returns: 2583

  43. {"72 -42","-13 40","-9 -41","30 -70"}

    696

    Returns: 3301

  44. {"77 -150","-60 141","31 -134"}

    615

    Returns: 3265

  45. {"-70 -47","-64 121","-68 -30","-55 -94"}

    259

    Returns: 615

  46. {"-26 -93","54 152","-8 -71","-73 -23","24 116","-29 -61","24 45","51 -46"}

    425

    Returns: 3354

  47. {"-59 -56","33 32","56 40","-21 118","-18 -148","81 -34","-82 156","68 -16"}

    436

    Returns: 3432

  48. {"71 -100","-3 -97","66 -154","20 -27","42 22","19 -98","26 160","-52 0","-34 -156"}

    258

    Returns: 2316

  49. {"-14 -33","5 103","16 130","-18 -47","47 -163","-88 -48","35 -164","-33 -27","-31 158"}

    483

    Returns: 3677

  50. {"-48 -162","-75 175","-6 -33","-82 156","-26 163","-42 21","12 147","-55 32","82 153"}

    221

    Returns: 1548

  51. {"-42 170","-53 -130"}

    694

    Returns: 986

  52. {"9 -12","59 -73","59 36","83 99","-4 98"}

    449

    Returns: 2538

  53. {"64 141","68 -30","-59 177","-60 60","-70 -109"}

    957

    Returns: 6654

  54. {"-5 -56","18 -150","72 101","-80 178","-35 -123","76 96","86 101"}

    644

    Returns: 4402

  55. {"64 60","0 99","18 25"}

    685

    Returns: 2351

  56. {"-23 176","-33 -60","-54 97","0 63","82 147"}

    28

    Returns: 219

  57. {"33 -176","-10 180","81 -79"}

    256

    Returns: 908

  58. {"10 175","-19 43","14 -132","4 4","-56 -21","-58 -81","-73 107"}

    865

    Returns: 6531

  59. {"-85 -145","13 157","-2 62","-73 78","18 70"}

    495

    Returns: 2571

  60. {"11 -32","-55 -133","0 42","-9 -70","87 53","-25 174","50 113","-17 -103","-12 41"}

    640

    Returns: 5307

  61. {"-3 162","34 -142"}

    172

    Returns: 386

  62. {"-53 87","-69 -163","3 67"}

    576

    Returns: 2136

  63. {"24 44","-21 174"}

    221

    Returns: 1033

  64. {"-26 52","77 -160","-4 59","-17 130","20 -66","76 -115","41 83","-2 158"}

    33

    Returns: 252

  65. {"-16 -27","-16 -156","-12 63","28 151","-60 12","88 14","10 -138","-64 56","30 35"}

    147

    Returns: 1305

  66. {"49 76","7 -27","-58 57","-24 -60","22 -177","60 70","-8 125"}

    838

    Returns: 6528

  67. {"83 -4","68 58","-19 -125"}

    103

    Returns: 473

  68. {"-49 -46","-8 82","-52 -92","14 52","0 -48"}

    557

    Returns: 3251

  69. {"-82 167","67 -76","76 54","-59 94"}

    73

    Returns: 459

  70. {"36 -16","-68 33","-69 27","8 115","16 -135"}

    699

    Returns: 5071

  71. {"41 -151","-40 -54"}

    828

    Returns: 3453

  72. {"-84 151","-1 116","11 154","-33 -129","48 -112","59 137","5 11","-50 -94","66 -44"}

    702

    Returns: 6494

  73. {"-29 -45","31 51","-60 106","40 -171","65 -85","64 -117","17 41","74 66"}

    657

    Returns: 5192

  74. {"-46 -155","37 -45","-26 5","-17 -54","56 -122","-73 -34","-28 15","-74 113"}

    524

    Returns: 3732

  75. {"49 145","42 -138","26 106","-18 115","50 80","31 106"}

    863

    Returns: 4268

  76. {"71 101","-20 -139","72 60","26 180","10 15","54 163"}

    240

    Returns: 1492

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: