洛谷 P1429 平面最近点对（加强版）

题目：平面最近点对（加强版）

 

思路：

点分治模板。

可参考这两位大佬的图解：

julao's blog QwQ

julao's blog QAQ

 

代码：（个人认为还比较好看233）

#include<bits/stdc++.h>
using namespace std;

#define maxn 200000
#define db double
#define inf (1<<30)

struct Pair{
	db x,y;
	bool operator <(const Pair& oth) const {
		return x<oth.x||(x==oth.x&&y<oth.y);
	}
};

int n;
Pair a[maxn+5];

void readin(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf%lf",&a[i].x,&a[i].y);
	}
	sort(a+1,a+n+1);
}

db findd(Pair x,Pair y){
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}

db slv(int l,int r) {
	if(l>=r) return inf;
	int mid=l+(r-l)/2;
	db d1=slv(l,mid),d2=slv(mid+1,r);
	db d=min(d1,d2),dmid=a[mid].x;
	vector<int> q1,q2;
	for(int i=l;i<=mid;i++) {
		if(fabs(a[i].x-dmid)<d) q1.push_back(i);
	}
	for(int i=mid+1;i<=r;i++) {
		if(fabs(a[i].x-dmid)<d) q2.push_back(i);
	}
	for(int i=0;i<q1.size();i++) {
		int x=q1[i];
		for(int j=0;j<q2.size();j++) {
			int y=q2[j];
			d=min(findd(a[x],a[y]),d);
		}
	}
	return d;
}

int main(){
	readin();
	db ans=slv(1,n);
	printf("%.4lf",ans);
	return 0;
}