POJ3714+最近点对

只需要特判标记即可

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
const double eps = 1e-8;
const double inf = 9999999999.0;
const int maxn =  100005;
struct Point{
	double x,y;
	int flag;
};
Point pnt[ maxn<<1 ],temp[ maxn<<1 ];
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 ){
		if( pnt[L].flag==pnt[R].flag )
			return inf;
		else
			return dis( pnt[L],pnt[R] );
	}
	int mid = (L+R)/2;
	double res,Ldis,Rdis;
	Ldis = solve( L,mid );
	Rdis = solve( mid+1,R );
	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];
		}
	}
	sort( temp,temp+cnt,cmpy );
	for( int i=0;i<cnt;i++ ){
		for( int j=i+1;j<cnt;j++ ){
			if( fabs( pnt[i].y-pnt[j].y )>res ) break;
			if( pnt[i].flag==pnt[j].flag ) continue;
			res = min( res,dis(pnt[i],pnt[j]) );
		}
	}
	return res;
}

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