神秘fabs
查看原帖
神秘fabs
274935
_Z_Y_X_楼主2023/10/29 17:55
#include <bits/stdc++.h>

using namespace std;
int n;
struct node{
	double x,y;
}p[200005],tmp[200005];
bool cmpx(node a,node b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
bool cmpy(node a,node b){
	return a.y<b.y;
}
double dis(node a,node b){
	return hypot(a.x-b.x,a.y-b.y);
}
double closest(int l,int r){
	if(l==r) return 1e20+0.1;
	if(l+1==r) return dis(p[l],p[r]);
	int mid=(l+r)/2;
	double d1=closest(l,mid);
	double d2=closest(mid+1,r);
	double ans=min(d1,d2);
	int k=0;
	for(int i=l;i<=r;i++){
		if(fabs(p[mid].x-p[i].x)<=ans) tmp[k++]=p[i];
	}
	sort(tmp,tmp+k,cmpy);
	for(int i=0;i<k;i++){
		for(int j=i+1;j<k;j++){
			if(fabs(p[j].y-p[i].y)>=ans) break;
			ans=min(ans,dis(tmp[i],tmp[j]));
		}
	}
	return ans;
}

合并的时候加上fabsWA了

去掉fabs过了

2023/10/29 17:55
加载中...