CLOSPT - Closest Points

no tags 

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

hide comments
:D: 2012-10-17 13:28:02

Yes, easily tutorial. Especially since O(N^2) is enough, so it's trivial.

Francky: 2012-10-17 11:27:36

There's still the same task, or harder ones on SPOJ classical. So this one belongs to tutorial, for sure.

Vikas Kushwaha: 2012-10-17 09:22:38

tutorial.


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