先来推荐几篇博客.其实大家只要认真看了这些博客,就没必要看我的了QWQ.
solve(V){
选择一条垂直分割线,它将V分割为V1,V2;
d=min(solve(V1),solve(V2));
取出垂直分割线往两端延伸d的区域内的所有点;
求出区域内最近距离d’;
return min(d,d’);
}
int n,b[200005];
struct point{
double x,y;
}a[200005];
bool cmpx(point x,point y){return x.x<y.x;}
bool cmpy(int x,int y){return a[x].y<a[y].y;}
double dis(point x,point y){
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
//l,r是点的下标,表示本次处理由第l~r个点构成的点集
double solve(int l,int r){
if(l==r)return 1e18;
if(l+1==r)return dis(a[l],a[r]);
//亲测:这一句可以不写,上面那个边界条件必须要写
int mid=(l+r)>>1;
//找到分割点,即点集中最中间的点
double d=min(solve(l,mid),solve(mid+1,r));
//分治
int k=0;
for(int i=l;i<=r;i++)
if(fabs(a[i].x-a[mid].x)<=d)b[++k]=i;
sort(b+1,b+k+1,cmpy);
for(int i=1;i<=k;i++)
for(int j=i+1;j<=k;j++)
if(a[b[j]].y-a[b[i]].y<=d)
d=min(d,dis(a[b[i]],a[b[j]]));
return d;
}
int main(){
n=read();
for(int i=1;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmpx);
printf("%.4lf\n",solve(1,n));
return 0;
}
int n;
struct point{
double x,y;
}a[200005],b[200005];
bool cmpx(point x,point y){return x.x<y.x;}
bool cmpy(point x,point y){return x.y<y.y;}
double dis(point x,point y){
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double solve(int l,int r){
if(l==r)return 1e18;
int mid=(l+r)>>1;
double midline=(a[mid].x+a[mid+1].x)/2;
//比较两份代码,就会发现,上面的分割线直接就是a[mid].x
//而这里的分割线是(a[mid].x+a[mid+1].x)/2
//显然此处更为严谨,这里以a[mid].x作为分割线会WA
double d=min(solve(l,mid),solve(mid+1,r));
int i=l,j=mid+1,k=i;
while(i<=mid&&j<=r){
if(cmpy(a[i],a[j]))b[k]=a[i],i++,k++;
else b[k]=a[j],j++,k++;
}
if(i<=mid)while(i<=mid)b[k]=a[i],i++,k++;
else while(j<=r)b[k]=a[j],j++,k++;
for(int i=l;i<=r;i++)a[i]=b[i];
int L=1,R=0;
for(int i=l;i<=r;i++)
if(fabs(a[i].x-midline)<=d){
while(L<=R&&(a[i].y-b[L].y)>=d)L++;
//优化时间复杂度,把一定不符合要求的点先去掉再进循环.
//这里没有的话就会TLE
for(int j=L;j<=R;j++)
d=min(d,dis(a[i],b[j]));
b[++R]=a[i];
}
return d;
}
原文:https://www.cnblogs.com/PPXppx/p/10363315.html