#include<iostream>
#include<cstdio>
#include<string> 
#include<algorithm>
#include<math.h>
using namespace std;
struct point{
	int flag;
	int x,y;
};
point s[200002];
int y[200002];
int t,n;
double max=9999999;
double dis(point p1,point p2){
	if(p1.flag==p2.flag)
		return 99999999;
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
bool cmpx(point p1,point p2){
	if(p1.x==p2.x) return p1.y<p2.y;
	return p1.x<p2.x;
}
bool cmpy(point p1,point p2){
	if(p1.y==p2.y) return p1.x<p2.x;
	return p1.y<p2.y;
}
int x_cmp(const void *a,const void *b){
	if(((point*)a)->x<((point*)b)->x)
		return -1;
	else return 1;
}
int y_cmp(const void*a,const void*b){
	if(s[(*(int*)a)].y<s[(*(int*)b)].y)
		return -1;
	else
		return 1;
}
double Nearest(int first,int last){
	if(last-first==1)
		return dis(s[first],s[last]);
	else if(last-first==2){
		double d1,d2,d3,d4;
		d1=dis(s[first],s[first+1]);
		d2=dis(s[first],s[first+2]);
		d3=dis(s[first+1],s[first+2]);
		d4=(d1<d2?d1:d2);
		return (d3<d4?d3:d4);
	}
	int mid=(first+last)/2;
	double min=(Nearest(first,mid)<Nearest(mid+1,last)?Nearest(first,mid):Nearest(mid+1,last));
	if(min==0)
		return 0;
	int y_end=0;
	int i,j;
	double d;
	for(i=mid;s[mid].x-s[i].x<min&&i>=first;i--)
		y[y_end++]=i;
	for(i=mid+1;s[i].x-s[mid].x<min&&i<=last;i++)
		y[y_end++]=i;
	qsort(y,y_end,sizeof(y[0]),y_cmp);
	for(i=0;i<y_end;i++){
		for(j=i+1;j<y_end&&s[y[j]].y-s[y[i]].y<min;j++){
			d=dis(s[y[i]],s[y[j]]);
			if(min>d)
				min=d;
		}
		//	min=(min<dis(s[y[j]],s[y[i]])?min:dis(s[y[j]],s[y[i]]));
	}
	return min;
}
int main(){
	int i,j;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d%d",&s[i].x,&s[i].y);
			s[i].flag=0;
		}
		for(i=n;i<2*n;i++){
			scanf("%d%d",&s[i].x,&s[i].y);
			s[i].flag=1;
		}
		qsort(s,2*n,sizeof(s[0]),x_cmp);
		printf("%.3f\n",Nearest(0,2*n-1));
	}
	return 0;
}

• Re:为什么会超时啊啊啊啊 (2130) Ali23333 2017-03-03 15:39:36
• Re:为什么会超时啊啊啊啊 (2130) 3145249016 2022-04-08 20:36:06