平面最近点对（加强版）

传送门

ovo原来简单版的非常的好做，只要肆意暴力枚举即可。

不过这道题的数据范围变成了200000，即使是洛谷神机也跑不过去的。

于是乎我们考虑分治法。

对于一个平面上的所有点，我们设其属于一个点集S。我们想要把点集S尽可能平均的分成两个点集，那么我们只要每次取当前点集中所有点的中位数进行分割即可。

记录dis表示一个点集之内两点的最短距离。对于一个点集S，将其分解为两个点集S1，S2之后，我们假设现在已经求出来S1的dis1，S2的dis2.那么当前的答案d=min（dis1，dis2），之后如果在S1，S2中还有点对的距离<d，那么一定分属于两个点集。

这个时候可以从中间的分割线分别向两边引出一条长度为d的矩形（记为C1，C2），能更新最近距离的点对一定分属于这两个矩形。然而单单这么分析的话最坏的复杂度仍然可能非常大。那我们用dis的性质来考虑一下，对于C1中的每一个点k，能与之配对更新最短距离的，一定是C2中一个长为dis，高为2*dis的一个矩形之内的点。再者，因为S2中每两个点的距离必须>=dis，所以这个矩形之内最多只可能有6个点。

也就是说对于C1中的每一个点k，最多只有6个点可以与之更新最短距离。那我们直接枚举这六个点并且更新就可以了。

所以我们一开始先把所有的点按照横坐标排序，先进行分割，之后分割到边界之后进行回溯合并，合并的时候我们枚举所以离中线的距离<=dis的点计入C1，C2，之后把这些点按照y值排序，之后进行配对更新即可，遇到不符合的情况要直接跳出，否则会T。（我就纳闷为什么照着人家写能慢了一倍）

看一下跑的贼慢的代码。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define repi,a,n) forint i = a;i <= n;i++)
#define peri,n,a) forint i = n;i >= a;i--)
#define enter putchar'
')
using namespace std;
typedef long long ll;
const int M = 200005;
const double INF = 9999999999;
int n,L,f[M],dp[M]; 
int read)
{
    int ans = 0,op = 1;
    char ch = getchar);
    whilech < '0' || ch > '9')
    {
    ifch == '-') op = -1;
    ch = getchar);
    }
    whilech >='0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar);
    }
    return ans * op;
}

struct node
{
    double x,y;
    bool operator < const node &g) const
    {
        ifx == g.x) return y < g.y;
        return x <  g.x;
    }
}s[M];

bool cmpint a,int b)
{
    return s[a].y < s[b].y;
}

double distint p,int q)
{
    return sqrts[p].x - s[q].x)*s[p].x - s[q].x) + s[p].y - s[q].y) * s[p].y - s[q].y));
}

double mergeint l,int r)
{
    double d = INF;
    ifl == r) return d;
    ifl+1 == r) return distl,r);//如果只有两个点就返回其间的距离
    int mid = l+r) >> 1;
    double d1 = mergel,mid);
    double d2 = mergemid+1,r);
    d = mind1,d2);
    int k = 0;
    repi,l,r) iffabss[mid].x - s[i].x <= d)) f[++k] = i;//记录所有离中线不超过dis的点
    sortf+1,f+1+k,cmp);
    repi,1,k)
    repj,i+1,k)
    {
    ifs[f[j]].y - s[f[i]].y >= d) break;
    double d3 = distf[i],f[j]);
    d = mind,d3);//进行答案更新
    }
    return d;
}

int main)
{
    n = read);
    repi,1,n) scanf"%lf %lf",&s[i].x,&s[i].y);
    sorts+1,s+1+n);
    printf"%.4lf
",merge1,n));
    return 0;
}

还有dalao跑的快一倍的代码。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1000001 ;
const int INF=2<<20;
int n,temp[maxn];
struct Point
{
    double x,y;
}S[maxn];

bool cmpconst Point &a,const Point&b)
{
    ifa.x==b.x)
        return a.y<b.y;
    else
        return a.x<b.x;
}

bool cmpsconst int &a,const int &b)
{
    return S[a].y<S[b].y ;
}

double mindouble a,double b)
{
  return a<b?a:b;
}

double distint i,int j)
{
    double x=S[i].x-S[j].x)*S[i].x-S[j].x);
    double y=S[i].y-S[j].y)*S[i].y-S[j].y);     
    return sqrtx+y);
}

double mergeint left,int right)
{
    double d=INF;
    ifleft==right)
        return d ;
    ifleft+1==right) 
        return distleft,right);
    int mid=left+right>>1;
    double d1=mergeleft,mid) ;
    double d2=mergemid+1,right) ;
    d=mind1,d2);
    int i,j,k=0;
    fori=left;i<=right;i++)
        iffabsS[mid].x-S[i].x)<=d)
            temp[k++]=i;
    sorttemp,temp+k,cmps);
    fori=0;i<k;i++)
        forj=i+1;j<k&&S[temp[j]].y-S[temp[i]].y<d;j++)
        {
            double d3=disttemp[i],temp[j]); 
            ifd>d3)
                d=d3;
        }
    return d;
}

int main)
{
    scanf"%d",&n);
    forint i=0;i<n;i++)
        scanf"%lf%lf",&S[i].x,&S[i].y);
    sortS,S+n,cmp);
    return !printf"%.4lf
",merge0,n-1));
}