CLOSE - So Close!

 

Given a set of points in the Euclidean space, find the distance between the closest pair of
points.

Given a set of points in the Euclidean space, find the distance between the closest pair of points.

Input

The first line of input will be the number of test cases. Each case start with a number N the number of points (1 <= N <= 100), The next N lines each has two numbers X and Y (-1000 <= X, Y <= 1000) representing the points coordinates.

Output

For each test case print “Case C: The shortest distance is X” without quotes where C is the case number starting with 1 and X is the distance between the closest pair of points in the points set. Show only and exactly 3 decimal numbers.

Example

Input:
2
6
1 3
3 5
8 7
5 6
2 0
7 5
3
329 56
363 147
376 387

Output:
Case 1: The shortest distance is 2.236
Case 2: The shortest distance is 97.144

Added by:hossamyosef
Date:2013-05-13
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:FCIS/ASU Local Contest 2013

hide comments
2013-05-14 08:06:02 Francky
I insist on one point : it's a bad idea to ask for text + float.
Please ask only for float answer and use judge n3 "ignore FP 10^-2", or 10^-6.
2013-05-14 07:53:25 hossamyosef
this problem had been tested by about 30 teams at our contest!!

Last edit: 2013-05-14 07:53:56
2013-05-13 13:51:44 Jacob Plachta
@Francky: Yeah, at least one problem already exists like this, and with large bounds that actually force an optimal algorithm.
2013-05-13 13:46:32 martinezgjuan
I'm getting WA for some strange reason. I've tried truncating to 3 decimals or rounding in different ways to the 3rd decimal.

Can you pleas check submission 9253624? Thanks!
2013-05-13 13:43:44 Francky
1) I'm rather sure such a task already exists in classical.
2) It's a bad idea to ask text + floating result ; what is the judge ???
3) I think it belongs to tutorial, and could be hidden if wrong data are confirmed.
2013-05-13 13:35:32 Jacob Plachta
Hmm, was the data definitely uploaded correctly on this one? It seems hard to get wrong.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.