Effective Sets

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!
Input
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.
Output
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.
Example
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
Author:  admin 
Tags  admin 
Date Added:  15102009 
Time Limit:  1  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
The problem statement says
The problem statement says "There may be more than one ships located at the same place", but I think in Example 1, there are two ships in (0,0). Am I right?
.....Woops I misunderstand
.....Woops I misunderstand the statement. Sorry.
In the first sample test,
In the first sample test, shouldn't the distance be 5 (its given 5.10)? or maybe even 0 for the ship located at 0,0 has its logically closest ship at 0,0
i think that for the first
i think that for the first test case the output must be
0 1
0 1
5 2
I also think the sample
I also think the sample output is wrong. It should be
0.00 1
0.00 1
5.00 2
1.41 2
5.00 4
6.40 4
2.83 2
1.41 1
For example, for the second sample test case and the first point, the effective value is two because the closest point to (5, 3) is (4, 4) at distance sqrt(2), and (3,1) has distance 2 * sqrt(2) which is no more than twice the radius.
It's definitely something
It's definitely something wrong with test cases, because even naive approach gets WA.
Admins check the test data, please.
We are looking into this.
We are looking into this.
do we have to read a blank
do we have to read a blank line after number of test cases as shown in example
and why C#2 not supported Its not telling any reason
Its quite strange that you
Its quite strange that you are still "looking into it" :P
So whats the correct output
So whats the correct output then . How can output be 5.10 in first case ?
My problems with codechef so far :
1) forgets my password.
2) Stuck at 26.2XXXXX in other problem.
3) Don't know output of this problem.
4) Usually loading of pages from site is slow.
But doesn't matter i suggest all this for improvement . You guys are doing a great job. Its a great initiative.
2AC so far. Is sample I/O
2AC so far. Is sample I/O
I think the test cases are
I think the test cases are correct and they concur with the problem statement.
The correct output for the examples is that given by Adrian Kuegel.
I dont know why but I am
I dont know why but I am getting SIGABRT runtime error on submitting my code for this problem.
Can some one plz suggest why I might be getting it.
There is nothing in the help section as well.
Hi... The radius of a ship is
Hi...
The radius of a ship is defined to be the distance from that ship to the ship closest to it.
So if the two ship are at same point, the distance has to be zero.
Please do the correction in the test cases.
Thanks
The sample I/O for this
The sample I/O for this problem has been fixed.
How can i take test
How can i take test case?
randomly.....
suggest me a way
I have two classes... how do
I have two classes... how do i upload or execute?
Kola: I came close to getting
Kola: I came close to getting disqualified last time I made such suggestions during a contest.
Aldrine: I believe you can package in a jarfile. The specs for it are somewhere here on the site. Sorry to be so vague, but I haven't had to do it yet myself.
what should be the answer for
what should be the answer for a case like
1(N)
1 2
as 1<=N<=30000
What should be the answer for
What should be the answer for n=1?
Admins please specify this.
What needs to be the output in case of infinity?
It took me 6 wrong
It took me 6 wrong submissions and over an hour to figure out what does codechef want for the trivial case of n=1.
I sincerely believe that it should be mentioned in the problem statement or at least admins should have replied to Giri's post a day ago. Admins here seem to be neglecting a lot comments which sincerely should be answered
it must be zero ...... as
it must be zero ......
as except itself no other ship is present........
hence o/p must be 0.00 0
correct me if i m wrong..................
@core2duo The problem
@core2duo The problem statement is clear enough to address your questions. There is only one way to interpret the statement.
administrator , due to the
administrator , due to the use of sqrt function the command gets executed with the command gcc <filename>.c lm
but if you execute the file with command gcc <filename>.c only and not use lm then the runtime error occurs so please tell me what should I do...
@Aniruddha The problem
@Aniruddha The problem statement does not mention what to print in the case of N=1 at all. It says to print out the distance from each ship to the nearest ship; that distance is undefined. It is most definitely not 0, which implies there is a second ship at exactly the same location.
The problem statement needs to be fixed.
Luckily i might have hit the
Luckily i might have hit the correct return for such case (N=1). because my solution has been accepted and i didn't take particular care of the case where N would be 1. Though i too think, that either the constraints should be 2<=N<=30000, or answer for N=1 should be mentioned clearly.
if i don't take any special
if i don't take any special case for n=1 in my program and take an input with n=1 i get a run time error on my pc . but the chef shows wrong answer . does tht mean mean tht n=1 is not the part of input ?? any one with successful submission for this problem submit a code where ur program produces run time error for n=1 (like divide by 0) and plz check ??
if not wht has to be the output for n=1??
Whats the intent ? Disqualify
Whats the intent ? Disqualify someone with correct submision or yourself.. (kidding about intent, but consequences will be these.)
So, what is the answer when N
So, what is the answer when N = 1? Am I wrong if I ask this? It's very confusing as the answer when N = 1 can't be determined only by reading the problem statement.
No, you aren't wrong to ask;
No, you aren't wrong to ask; I'm surprised the admin haven't fixed the problem statement yet.
Updated. There is no test
Updated. There is no test case with N = 1.
hey guys i am new to
hey guys i am new to codecheff can u give me some tips on how to deal with time limit exceeded???
@Admin could you add the data
@Admin could you add the data set also?
I am not sure why did i get WA.