| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1138
Help phunter's friend
Time Limit: 3000ms
Memory Limit: 65536kb Description
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? Input
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.
Output
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 |