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

【分治】P1429 平面最近点对(加强版)

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

给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的

 

将每个带求的区间分成左右两部分来处理,当前已知左和右的最小距离,那么只需要与跨过分界线的距离比较即可!

分而治之,分很好处理,这个合并设计到几处比较的过程

设minn为左右半边的最小点对值。

然后以mid这个点为中心,扩展宽为2minn,长为2minn的正方形。

除了这个正方形外的点都不可能使答案更小。

 

 

代码

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
double inf=1e18;
ll n;
struct point 
{
	double x,y;
}p[maxn];
bool cmp(point aa,point bb)
{
	if(aa.x!=bb.x) return aa.x<bb.x;
	return aa.y<bb.y;
}
double calc(int x,int y)
{
	return sqrt((p[x].x-p[y].x)*(p[x].x-p[y].x)+(p[x].y-p[y].y)*(p[x].y-p[y].y));
}
ll s[maxn];
bool CMP(int x,int y)
{
	return p[x].y<p[y].y;
}
double solve(int l,int r)
{
	double d=inf;
	ll mid=l+r>>1;
	if(l==r) return d;
	if(l+1==r) return calc(l,r);
	double d1=solve(l,mid);
	double d2=solve(mid+1,r);
	d=min(d,d1); d=min(d,d2);
	int cnt=0;
	for(int i=l;i<=r;i++)
		if(abs(p[i].x-p[mid].x)<=d) 
			s[++cnt]=i;
	sort(s+1,s+cnt+1,CMP);
	for(int i=1;i<=cnt;i++)
		for(int j=i+1;j<=cnt && abs(p[s[i]].y-p[s[j]].y)<d;j++)
			d=min(d,calc(s[i],s[j]));
	return d;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    sort(p+1,p+n+1,cmp);
    printf("%.4lf",solve(1,n));
    return 0;
}