SPOJ.com - Problem CLOPPAIR

CLOPPAIR - Closest Point Pair

#geometry

You are given N points on a plane and your task is to find a pair of points with the smallest Euclidean distance between them.

All points will be unique and there is only one pair with the smallest distance.

Input

First line of input will contain N (2<=N<=50000) and then N lines follow each line contains two integers giving the X and Y coordinate of the point. Absolute value of X,Y will be at most 10^6.

Output

Output 3 numbers a b c, where a, b (a<b) are the indexes (0 based) of the point pair in the input and c is the distance between them. Round c to 6 decimal digits.

See samples for more clarification.

Input: 
5 
0 0
0 1
100 45
2 3
9 9

Output: 
0 1 1.000000

Input: 
5
0 0
-4 1
-7 -2
4 5
1 1

Output: 
0 4 1.414214

Submit solution!

hide comments

< Previous 1 2 3 4 5 Next >

	darshit05: 2017-10-04 13:05:27 For test case 12 use std::fixed; before using std::setprecision(6);
	miaortizma: 2017-08-20 03:46:02 12th case solved by checking my minimum (default) distance.
	bruceoutdoors: 2017-08-19 18:01:53 also this problem was never pass with python. The time limit set is too little!
	bruceoutdoors: 2017-08-19 17:52:06 I used double instead of long long int and still passed (?_?)
	bruceoutdoors: 2017-08-19 17:29:35 omg guys. I managed to get past test case 12. So what happened was that my solution was correct, but because I used cout with setprecision(7), it displayed the wrong answer for some reason. So if you want to pass this challenge, use printf update: lol I realized I need to use fixed with setprecision to get it to the right decimal places. cout << setprecision(6) << fixed << distance; Last edit: 2017-08-19 17:34:00
	AAKASH TYAGI: 2016-12-30 21:10:00 Remember to print the smaller index first
	abhishekrahul: 2016-12-17 15:54:49 can anyone provide me fully accepted code for this question ,, i am trying it from two days but always getting wa near test case 12 ....
	anshal dwivedi: 2016-03-23 09:39:42 Use long long int: ) , using double caused me 4 WA on test case 12 ;(
	kr1996: 2016-01-19 21:48:24 12th case WA is probably because of the (a<b) condition
	Sudharsansai: 2016-01-07 15:07:09 Don't use long long...May get WA becoz of that.Use double.Comparisons are not that strict !! Attention to (a<b) in output .( WA becoz of that -_-) . Can use SPOJ TOOLKIT to get test cases. But some solutions there, are wrong ( Verified using my Brute Force checker) . But those solutions are accepted here. Wish to know whether the test cases here are weak ?? Last edit: 2016-01-07 15:07:37

Submit solution!

Added by:	SALVO
Date:	2011-04-14
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Standard Problem