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

分治——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;
}