Problem 1138
Help phunter's friend
Time Limit: 3000ms
Memory Limit: 65536kb
The former board master of Algorithm of USTCbbs, id=phunter, majoring in high energy physics, is now working at Large Hadron Collider (LHC), at Geneva,Switzerland for his PhD. One day, a friend, Pieter, came to his office and seek help to search for a new particle.
High energy people use decay-mode to find new particles. Pieterproposed a new particle called Hoggs (not Higgs), which can decay to 4 photon particles. In experimental point of view, this decay-mode shows 4 charge-less particles that these 4 particles come from the same point at the center of the collider, then shoot out to 4 close directions. For every particle, two values, Eta and Phi, are used to define its direction. Among all the particles, one and 3 its closest neighbors will be listed in a group, as the a candidate of Hoggs. The distance between two particles is defined as R=sqrt(Eta*Eta+Phi*Phi).
Phunter says, why not just use brute force, is it OK? Unfortunately, it is LHC. There are too many particles and large quantity of data to process. Speed is vital. Pieter has tested that it is super slow if brute force for O(n*n). Can you help Pieter to speed it up, and let Pieter buy phunter a coffee?
The input consists of a single test case, and all of it's lines follow the same format. Each line has three values separated by an amount of white space. The first value is the unique id number of that particle, expressed as an integer. The second value is the Eta, as double. The third and last value is the Phi, expressed as double. Every particle has its unique Eta and Phi values. Each line ends with a single new line, except for the last line of the file, which may or may not have a terminating new line. The input file is well formed. There won't be more than 20000 lines.
In the order presented in the input file, output the nearest three particles for each particle. Each line of output should start with the integer id of the particle followed by a single space character, and then the list of three nearest other particle ids followed by a single new line. Even the last line of the output should terminate in a new line. This list should be comma-delimited, with no spaces. The list must be in order of proximity, with the closest of the three being first, and the farthest of the three being last.
Sample Input
1  0.0      0.0
2  10.1     -10.1
3  -12.2    12.2
4  38.3     38.3
5  79.99    179.99
Sample Output
1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 0.8ms with 1 query(s).