分治中距离中线的距离小于d忘记加绝对值了也能过属实逆天

感兴趣的可以看代码

#include<bits/stdc++.h>
#define ll long long 
#define reg register
#define db double
#define il inline
using namespace std;
const int N=200005;
int n;
double ans=1e10;
struct node{
	double x,y;
}z[N],book[N];
 int tmp[N];
bool cmp(node a,node b){
	if(a.x!=b.x)
	return a.x<b.x;
	else 
	return a.y<b.y;
}
il double dis(int x,int y){
	return sqrt((z[x].x-z[y].x)*(z[x].x-z[y].x)+(z[x].y-z[y].y)*(z[x].y-z[y].y));
}
double dfs(int l,int r){
	if(l==r)return 1e10;
	if(l==r-1){
		ans=min(ans,dis(l,r));
		if(z[l].y>z[r].y)swap(z[l],z[r]);
		return dis(l,r);
	}
	int mid=(l+r)/2;
	double a=z[mid].x;
	double d=min(dfs(l,mid),dfs(mid+1,r));
	int tot=0;
	int c=l,dd=mid+1,cnt=l-1;
	while(c<=mid&&dd<=r){
		if(z[c].y>z[dd].y){
			book[++cnt]=z[dd++];
		}else{
			book[++cnt]=z[c++];
		}
	}
	if(c<=mid){
		while(c<=mid)book[++cnt]=z[c++];
	}else if(dd<=r){
		while(dd<=r)book[++cnt]=z[dd++];
	}
	for(reg int i=l;i<=r;i++)z[i]=book[i];
	cnt=0;
	for(reg int i=l;i<=r;i++){
		if(a-z[i].x<d)tmp[++cnt]=i;
	}
	for(reg int i=1;i<=cnt;i++){
		for(reg int j=i+1;j<=cnt&&z[tmp[j]].y-z[tmp[i]].y<d;j++){
			d=min(d,dis(tmp[i],tmp[j]));
		}
	}
	ans=min(ans,d);
	return d;
}
int main(){
	scanf("%d",&n);
	for(register int i=1;i<=n;i++){
		scanf("%lf%lf",&z[i].x,&z[i].y);
	}
	sort(z+1,z+1+n,cmp);
	dfs(1,n);
	printf("%.4lf",ans);
	return 0;
}