平面最近点对（分治）

妩媚的ak萝莉 · 2019-09-25 16:18:01 · 题解

本题言简意赅，给n个点，求最近点对(n\le 10^5)

Luogu

poj(略有不同)

题解：

这题初看令人眩晕，有效信息两两点的距离就有O(n^2)，只能是减一些状态。比如说\Delta x \Delta y都更大就舍去？？明显没有可操作性。。

正解是一个经典分治，本题分治特点是利用分治答案来进行分治，按x排序，按x分治，枚举mid左右ans范围内的点，把这些点按y排序，y坐标相差不超过ans的点统计答案（横着的日字划分，可证每个点统计答案不超过6个），总复杂度O(6nlog^2n)

具体的说，本题是一个经典的模型，本来O(n^2)无法优化的状态数，通过分治下一个“自矛盾”巧妙地避免了枚举明显不可能的点对。跨边界的可能是答案的点对其实只有一点点，什么“自矛盾”，其实就是根据左右已统计的答案严谨地证明了这个“一点点”

代码（Luogu）：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long double ld;
const int N=2e5+50;
const ld le=1e-7;
const ld INf=2000000000.0;
struct Point{
    int x,y;
    Point(){}
}po[N],tmp[N];
int n;
ld ans=INf;

bool cmpx(Point a,Point b){return a.x<b.x;}

bool cmpy(Point a,Point b){return a.y<b.y;}

inline int wdabs(int a){return (a>0?a:(-a));}

inline ld sqr(ld a){return a*a;}

inline ld dis(int a,int b){return sqrt(sqr(tmp[a].x-tmp[b].x)+sqr(tmp[a].y-tmp[b].y));}

void solve(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)/2;
    solve(l,mid);
    solve(mid+1,r);
    int d=ans,cnt=0;d+=1;
    for(int i=l;i<=r;i++)
        if(wdabs(po[i].x-po[mid].x)<=d)
            tmp[++cnt]=po[i];
    sort(tmp+1,tmp+1+cnt,cmpy);
    for(int i=1;i<=cnt;i++)
    {
        for(int j=i+1;tmp[j].y-tmp[i].y<=d && j<=cnt;j++)
            ans=min(ans,dis(i,j));
    }
    return;
}

int main()
{
    ans=INf;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&po[i].x,&po[i].y);
    sort(po+1,po+1+n,cmpx);
    solve(1,n);
    printf("%.4Lf\n",ans);
    return 0;
}