HDU1007+最近点对

模板题，不解释。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
using namespace std;
const double eps = 1e-8;
const int maxn = 100005;
const double inf = 9999999999.0;
struct Point {
	double x,y;
};
struct Line{
	Point a,b;
};
Point pnt[ maxn ],temp[ maxn ];
double dis( Point a,Point b ){
	return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
int cmpxy( Point a,Point b ){
	if( a.x!=b.x )
		return a.x<b.x;
	else
		return a.y<b.y;
}
int cmpx( Point a,Point b ){
	return a.x<b.x;
}
int cmpy( Point a,Point b ){
	return a.y<b.y;
}

double solve( int L,int R ){
	if( L==R )
		return inf;
	if( L+1==R )
		return dis( pnt[L],pnt[R] );
	int mid = (L+R)/2;
	double Ldis,Rdis;
	Ldis=solve( L,mid );
	Rdis=solve( mid+1,R );
	double res = min( Ldis,Rdis );
	int cnt = 0;
	for( int i=L;i<=R;i++ ){
		if( fabs( pnt[i].x-pnt[mid].x )<=res ){
			temp[ cnt++ ] = pnt[i];
		}
	}//分离出宽度为RES的点
	sort( temp,temp+cnt,cmpy );
	for( int i=0;i<cnt;i++ ){
		for( int j=i+1;j<cnt;j++ ){
			if( fabs(temp[i].y-temp[j].y)>res ) break;
			res = min( res,dis(temp[i],temp[j]) );
		}
	}
	return res;
}

int main(){
	int n;
	while( scanf("%d",&n),n ){
		for( int i=0;i<n;i++ )
			scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
		sort( pnt,pnt+n,cmpxy );
		double Ans = solve( 0,n-1 );
		printf("%.2lf\n",Ans/2.0);
	}
	return 0;
}