Post Offices

Time Limit: 10 Seconds    Memory Limit: 65536 KB

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 (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 (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)

Sample Input

N/A – binary file

Sample Output

N/A – binary file
Submit

Source: South Eastern European Regional Contest 2011