Post Offices
You are given the location of all post offices on earth, and a set of destinations for various packages that need to be shipped. For each package, you need to find the maximal set of post offices that are suitable as destinations for the package –i.e. the set of post offices must satisfy the following constraints:
The post office that is closest to the final destination must be in the result set.
All post offices that are at most 2% farther than the closest post office must also be present in the result set.
For the purpose of this problem, the earth is approximated to be a perfectly flat sphere, with the radius 6381 Km. The distance between two points may be computed using the haversine formula:
A = sin( (lat1-lat2)/2)^2 + cos(lat1) · cos(lat2) · (sin((long1-long2)/2)^2);
DISTANCE = 6381 · 2 · atan2(sqrt(A), sqrt(1-A));
(you may use other formulas if you please, but note that the arccosine formula has large rounding errors for small distances, and thus you may get wrong results).
Input
The input file is a binary file; all numbers written in it are written in little-endian representation. It contains, in this order:
4 bytes that represent the number of post offices N – integer number, no greater than 3000000
For each post office, the input file contains two numbers <LAT LONG> (4 bytes each) representing the latitude and longitude (in degrees) of the post office. The numbers are single-precision IEEE754 floating point numbers. All latitudes are between -90 and 90 degrees; all longitudes are between -180 and 180 degrees.
4 bytes representing the number of packages M (integer number, no greater than 500000)
For each package, the input file contains two numbers <LAT LONG> (4 bytes each) representing the latitude and longitude (in degrees) of the destination. The numbers are single-precision IEEE754 floating point numbers. All latitudes are between -90 and 90 degrees; all longitudes are between -180 and 180 degrees.
Output
The output file is also a binary file, containing only 32-bit integers written in little-endian representation. For each of the M lines in the input file, it must contain:
One integer –the number P of post offices in the destination set
P integers – the indices of the post offices in the destination set, sorted in ascending order (lower indices first). The index of the first post office in the input file is considered to be 1 (and thus, all indices should be between 1 and N, inclusively)