CLOSPT - Closest Points

Determine the square of the distance between the closest two points in a set of points. For example, among the points (1,1), (5, 1), and (1,3), the closest distance between two points is 2, the distance between (1,1) and (1,3). So the correct output is 22 = 4.

Input:
The first line is the number of points
Each subsequent line is the X and Y coordinates (positive integers) of one point, separated by a space

Output:
The square of the minimum distance between two of the input points, as an integer.

 

Input Output
3
1 1
5 1
1 3
4
8
5 3
4 9
13 9
16 11
22 9
12 1
8 3
9 1
5
4
3 2
9 4
7 2
1 14
8

Added by:Ben Dilts
Date:2012-10-13
Time limit:6.768s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2012-10-17 13:28:02 :D
Yes, easily tutorial. Especially since O(N^2) is enough, so it's trivial.
2012-10-17 11:27:36 Francky
There's still the same task, or harder ones on SPOJ classical. So this one belongs to tutorial, for sure.
2012-10-17 09:22:38 Vikas Kushwaha
tutorial.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.