欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷 P1429 平面最近点对(加强版)

程序员文章站 2022-03-03 08:23:41
...

题目:平面最近点对(加强版)

 

思路:

点分治模板。

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

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;
}

 

相关标签: 点分治