TopCoder problem "Satellites" used in SRM 180 (Division I Level Three)

Problem Statement


A government agency plans to establish a network of satellites to monitor rocket launches worldwide. You have been asked to develop a simulation that will help assess the coverage of a given satellite configuration. Given a collection of satellite positions and a collection of launch positions, you are to determine which rockets can be accurately detected before they leave boost phase.

For the purpose of this simulation, the Earth is a sphere with a diameter of 12800 kilometers. When a rocket is launched, it flies straight up from the surface. All satellites operate at an altitude between 200 and 1200 kilometers, inclusive, and hold their position for the duration of the simulation. A rocket can be accurately detected only if it is visible to at least three satellites when its boosters are depleted at the altitude of 400 kilometers. In order to preclude floating-point error, the simulation will not include cases in which the line between a satellite and a rocket at the 400-kilometer altitude passes within one millimeter of the Earth.

The locations of the rocket launches are specified by a String[], rockets, each element of which contains exactly 19 characters. The first nine characters encode a fixed-point number in the following manner: the first character is either plus ('+') or minus ('-'); the next four characters are the integer part of the number, padded with zeros as necessary; the next character is the decimal point ('.'); the final three characters are the zero-padded fractional part of the number. This number gives the latitude of the rocket launch. The tenth character of each element in rockets is a space, and the last nine characters give the longitude of the corresponding rocket in the same fixed-point format.

Latitudes range between -90.0 and 90.0 degrees, inclusive, while longitudes range between -180.0 and 180.0 degrees, inclusive. The equator is at latitude zero; the North Pole, at 90 degrees; the South Pole, at -90 degrees. Longitude zero runs through the Greenwich Royal Observatory in London. Positive longitudes are measured to the east of Greenwich, negative ones to the west. Longitudes 180 and -180, which are one and the same, lie on exactly the opposite end of the globe from longitude zero. If a rocket were launched from the Eiffel Tower, for example, its location would be given as "+0048.867 +0002.267".

The locations of the satellites are described by another String[], satellites, each element of which contains exactly 29 characters. The first 19 characters encode the latitude and longitude, just as for rocket launches, of the terrestrial point closest to the satellite. The 20th character is a space, and the last nine characters give the satellite's distance in kilometers from the Earth's surface, again using the same fixed-point format. For example, a satellite flying at an altitude of 550 kilometers over Mount Everest would have the location "+0027.988 +0086.925 +0550.000".

You are to return a int[] containing the zero-based indices, sorted by ascending value, of those rockets that can be detected at an altitude of 400 kilometers by at least three satellites.



Parameters:String[], String[]
Method signature:int[] detectable(String[] rockets, String[] satellites)
(be sure your method is public)


-This simulation ignores collisions. Several satellites or rockets, or both, may occupy the same point at the same time.


-rockets contains between 1 and 50 elements, inclusive
-each element of rockets conforms to the format described above
-satellites contains between 1 and 50 elements, inclusive
-each element of satellites conforms to the format described above
-the input is such that no line of sight between a satellite and a rocket at the 400-kilometer altitude passes within one millimeter of the Earth


{"+0000.000 -0000.000"}
{ "+0000.000 -0000.000 +0200.000",
  "+0000.000 -0000.000 +0400.000",
  "+0000.000 -0000.000 +1200.000"}
Returns: { 0 }
All satellites are at the same latitude and longitude as the rocket, so all can see it. Note that satellites do not block one another's lines of sight.
{"-0050.000 +0045.000","+0040.000 -0135.000"}
{"+0090.000 +0000.000 +1200.000",
 "-0090.000 +0000.000 +1200.000",
 "+0000.000 +0000.000 +1200.000",
 "+0000.000 -0090.000 +1200.000",
 "+0000.000 +0180.000 +1200.000",
 "-0000.000 -0045.000 +1200.000",
 "-0000.000 -0135.000 +1000.000",
 "-0011.000 -0136.000 +1086.828"}
Returns: { 1 }
Satellites 0, 6, and 7 can see rocket 1, their lines of sight coming within about 59.593, 215.477, and 0.000177 kilometers of the Earth's surface, respectively. Only satellite 1 can see rocket 0.
{"+0037.431 -0143.361",
 "+0037.443 -0143.375",
 "+0037.413 -0143.364"}
{"+0037.470 -0143.316 +0513.143",
 "+0037.443 -0143.388 +0342.159",
 "+0037.434 -0143.361 +1034.123"}
Returns: { 0,  1,  2 }
All satellites and rockets are within a single degree of latitude and longitude of one another's locations; hence, all rockets are visible to all three satellites.

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories: