平面最近点对，是指给出平面上的n个点，寻找点对间的最小距离
首先可以对按照x为第一关键字排序，然后每次按照x进行分治，左边求出一个最短距离d1，右边也求出一个最短距离d2,那么取d=min(d1, d2)
然后只需考虑横跨左右两侧的点，不妨枚举左侧的点pi
那么很显然的是如果pi距离中间的点超过了d，便可以直接舍去，只需考虑距离中间点小于d的点
这样一来就可以对每个pi画一个边长为2d的正方形，易证，矩形内最多存在8个点。
那么关键问题就是要快速找这8个点
朴素做法是对分治后的点进行快排，这样复杂度就是nlognlogn
但是我们如果结合归并排序，每一次分治的过程顺带就按y归并排序，便可以把logn省掉了 （%%%想出做法的和鑫神犇）
代码如下
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
struct P
{
int x, y;
bool operator <(const P& B)const { return x < B.x; }
}p[];
int dis(P &A, P &B) { return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y); }
P Q[];
int Divide(int l, int r)
{
if(l == r) return 1e7;
int mid = (l+r)>>, d, tx = p[mid].x, tot = ;
d = min(Divide(l, mid), Divide(mid+, r));
for(int i = l, j = mid+; (i <= mid || j <= r); i++)
{
while(j <= r && (p[i].y > p[j].y || i > mid)) Q[tot++] = p[j], j++; //归并按y排序
if(abs(p[i].x - tx) < d && i <= mid) //选择中间符合要求的点
{
for(int k = j-; k > mid && j-k < ; k--) d = min(d, dis(p[i], p[k]));
for(int k = j; k <= r && k-j < ; k++) d = min(d, dis(p[i], p[k]));
}
if(i <= mid) Q[tot++] = p[i];
}
for(int i = l, j = ; i <= r; i++, j++) p[i] = Q[j];
return d;
} int main()
{
int n;
cin>>n;
for(int i = ; i <= n; i++) cin>>p[i].x>>p[i].y;
sort(p+, p++n);
cout<<Divide(, n)<<endl;
}
注意：这里只选了坐标为整数的点，而且范围较小，需要一定的更改才能使用