题解 P1429 【平面最近点对（加强版）】

· · 题解

为什么要分治啊？暴力枚举就可以了。。。。。。

虽然正常枚举O(n^2)无法承受，但是可以先排序，在每次枚举前确定一个枚举上界，如果x坐标差超过了这个上界，答案不会更优，直接弹出。时间复杂度O(能过)。

代码：

#include<bits/stdc++.h>
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define Forward(i,a,b) for(i=(a);i>=(b);--i)
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
template<typename T>inline void read(T &x)//读入优化
{
    T s=0,f=1;char k=getchar();
    while(!isdigit(k)&&(k^'-'))k=getchar();
    if(!isdigit(k)){f=-1;k=getchar();}
    while(isdigit(k)){s=s*10+(k^48);k=getchar();}
    x=s*f;
}
void file()
{
    #ifndef ONLINE_JUDGE
        freopen("dist.in","r",stdin);
        freopen("dist.out","w",stdout);
    #endif
}
const int MAXN=200010;
int n;
typedef pair<int,int>Pr;//点
Pr a[MAXN];
void init()
{
    read(n);
    Rep(i,1,n)read(a[i].first),read(a[i].second);
    sort(a+1,a+n+1);//排序
}
long long ans;
long long dist(int x,int y)//求距离
    {return (long long)(a[x].first-a[y].first)*(a[x].first-a[y].first)
        +(long long)(a[x].second-a[y].second)*(a[x].second-a[y].second);}
#define Chkmin(a,b) a=a<b?a:b
void search(int poi,long long &r)//暴力搜索
{
    Rep(i,poi+1,n)
    {
        if((a[i].first-a[poi].first)*(a[i].first-a[poi].first)>=r)return;//答案不会更优，弹出
        Chkmin(r,dist(poi,i));
    }
}
void solve()
{
    ans=dist(1,2);//先确认第一个上界
    Rep(i,1,n)search(i,ans);//再搜索
    printf("%.4lf\n",sqrt(ans));//记得别先开方，防止精度误差
}
int main()
{
    file();
    init();
    solve();
    return 0;
}