分治——Luogu1429 平面最近点对(加强版)
程序员文章站
2022-05-12 15:01:14
...
题面:Luogu1429
关于求平面最近点对的方法有很多很多。。。
像是那种随机旋转角度然后暴力算的这种方法就很鬼畜QAQ
靠谱一点的算法呢就是分治了
我们计算区间l~r的最近距离
首先计算l~mid和mid~r的最近距离,然后考虑一下mid左边和mid右边对答案的贡献
首先记录下dist=min(l~mid答案,mid~r答案),然后把左边x坐标与mid的差小于等于dist的点统计出来,再把右边x坐标与mid的差小于等于dist的点统计出来
然后左边右边暴力判断统计答案就行了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<set>
#include<map>
#include<string>
#include<ctime>
#include<queue>
#include<vector>
using namespace std;
inline double sqr(double x){return x*x;}
struct ppap{double x,y;}a[200001];
ppap p1[200001],p2[200001];
inline bool cmp(ppap a,ppap b){return a.x==b.x?a.y<b.y:a.x<b.x;}
int n,pp1,pp2;
inline double work(int l,int r){
double ans=1e9;
if(l==r)return ans;
if(l+1==r)return sqr(a[l].x-a[r].x)+sqr(a[l].y-a[r].y);
int mid=l+r>>1;
ans=min(work(l,mid),work(mid,r));
pp1=pp2=0;
for(int i=l;i<mid;i++)if(sqr(a[mid].x-a[i].x)<=ans)p1[++pp1]=a[i];
for(int i=mid+1;i<=r;i++)if(sqr(a[i].x-a[mid].x)<=ans)p2[++pp2]=a[i];
for(int i=1;i<=pp1;i++)
for(int j=1;j<=pp2;j++){
double d=sqr(p1[i].x-p2[j].x)+sqr(p1[i].y-p2[j].y);
ans=min(ans,d);
}
return ans;
}
int main()
{
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,cmp);
printf("%.4lf",sqrt(work(1,n)));
return 0;
}