All submissions for this problem are available.
Johnny has been hired to write a program to analyse strategic data for the Bytelandian Navy. His task is described below.
There are N battleships represented as N points on the plane. The radius of a ship is defined to be the distance from that ship to the ship closest to it. The effective set for a ship is defined to be the set of all ships (excluding itself) which are at a distance from that ship of no more than twice its radius. The number of elements in the effective set of a ship is called the effective value of that ship.
Johnny needs to write a program to calculate the radius and the effective value of each battleship. This task is so tough that without your help, Johnny could never finish it. Let's help him!
The first line contains t, the number of test cases (about 5). Then t test cases follow. Each test case has the following form:
- The first line contains an integer N, the number of battleships (1 <= N <= 30000).
- Each line in the next N lines contains two integers X, Y (0 <= X, Y <= 10000) represents the coordinates of a battleship.
Each test case's input is separated by a blank line. There may be more than one ships located at the same place.
For each test case, print N lines. Each line should contain two numbers which are the radius and the effective value of the corresponding battleship. The radius should be rounded to 2 decimal points.
Print a blank line after each test case's output.
Input 2 3 0 0 0 0 3 4 5 5 3 7 8 0 9 3 1 4 4 Output 0.00 1 0.00 1 5.00 2 1.41 2 5.00 4 6.40 4 2.83 2 1.41 1
|Time Limit:||1 - 2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLPS, CPP 4.9.2, CS2, D, FORT, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC|
Fetching successful submissions