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.

Definition

Notes

Constraints

Examples