[UVa] 10245 - The Closest Pair Problem

題目網址: http://goo.gl/V05Uho

題意:
(from luckycat)


解 法: 蠻經典的 divide and conquer 題目，把點依照先 x 後 y 排序後，二分所有的點，算出左右兩部分的最小距離之後，再檢查中間有可能為最小距離的點對。

TAG: Divide and Conquer,

注意:

程式碼:

	/**
	* Tittle: 10245 - The Closest Pair Problem
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/26
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	#include <cmath>
	#include <vector>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define INF 1e4
	#define N 10005
	struct Point {
	double x, y;
	Point( double _x=0, double _y=0 ):
	x(_x), y(_y) {}
	inline const bool set( void ) {
	return scanf( "%lf%lf", &x, &y )==2;
	}
	const bool operator<( const Point &op ) const {
	if( x == op.x ) return y < op.y;
	return x < op.x;
	}
	const double disSqr( const Point &op ) const {
	return (x-op.x)*(x-op.x)+(y-op.y)*(y-op.y);
	}
	};
	typedef vector<Point> VP;
	// declarations
	int n;
	Point p[N];
	// functions
	double closest( int l, int r )
	{
	if( l >= r ) return INF*INF;
	if( l+1 == r )
	return p[l].disSqr( p[r] );
	int mid = (l+r)>>1;
	double mind = min( closest(l,mid), closest(mid+1,r) );
	VP bucket1, bucket2;
	for( int i=mid; i>=l && (p[mid].x-p[i].x)<mind; --i )
	bucket1.push_back(p[i]);
	for( int i=mid+1; i<=r && (p[i].x-p[mid].x)<mind; ++i )
	bucket2.push_back(p[i]);
	FOR( i, 0, bucket1.size()-1 ) FOR( j, 0, bucket2.size()-1 )
	mind = min( mind, bucket1[i].disSqr( bucket2[j] ) );
	return mind;
	}
	// main function
	int main( void )
	{
	double ans;
	// input
	while( scanf( "%d", &n )==1 && n ) {
	FOR( i, 1, n ) p[i].set();
	// solve
	sort( p+1, p+1+n );
	// output
	ans = sqrt(closest( 1, n ));
	if( ans >= INF ) puts("INFINITY");
	else printf( "%.4lf\n", ans );
	}
	return 0;
	}

view raw 10245 - The Closest Pair Problem.cpp hosted with ❤ by GitHub