题目：题目链接
一 问题描述
假设平面内有N个点，每个点以坐标（x, y)给出，N的数据量很大，如何求出其中最近的两个点。
二 算法
一种方法是暴力，通过枚举任意两个点，找到最小的，一共要比较C(n, 2)次，故实践复杂度为O(n2)，超时。
另外一种就是分治法，步骤为：
1把所有点按x坐标的大小排序，从中间一份为二。
2最近点对有三种情况，都在左边，都在右边，左右都有递归求出都在左边和都在右边的情况，选一个最小值curmin。
3然后求出两边各有一个的情况得结果为tmp。
4取tmp和curmin的最小值为结果
赤裸裸的套模版，上代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
int min(int a, int b)
{
if(a<=b)
return a;
return b;
}
int max(int a, int b)
{
if(a>=b)
return a;
return b;
}
double min(double a, double b)
{
if(a<=b)
return a;
return b;
}
double max(double a, double b)
{
if(a>=b)
return a;
return b;
}
#define N 100100
struct node
{
double x,y;
} g[N];
node save[N];
int cmp(node t,node t1)
{
return t.x<t1.x;
}
int cmp1(node t,node t1)
{
return t.y<t1.y;
}
double cal(node t,node t1)
{
return sqrt((t.x-t1.x)*(t.x-t1.x)+(t.y-t1.y)*(t.y-t1.y));
}
double fuc(int b,int d)
{
if(d-b==1) return cal(g[b],g[d]);
if(d-b==2)
{
return min(cal(g[b],g[b+1]),min( cal(g[b],g[d]),cal(g[b+1],g[d])));
}
int mid=(b+d)/2;
double mi=min(fuc(b,mid),fuc(mid+1,d));
for(int i=mid-1; i>=b; i--)
{
if(g[mid].x-g[i].x>mi)
{
b=i;
break;
}
}
for(int i=mid; i<=d; i++)
{
if(g[i].x-g[mid-1].x>mi)
{
d=i;
break;
}
}
int cnt=0;
for(int i=b; i<=d; i++)
save[cnt++]=g[i];
sort(save,save+cnt,cmp1);
for(int i=0; i<cnt; i++)
for(int j=i+1; j<cnt; j++)
{
if(save[j].y-save[i].y>mi) break; // 这步优化很是重要
if(cal(save[i],save[j])<mi) mi=cal(save[i],save[j]);
}
return mi;
}
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
for(int i=0; i<n; i++)
{
scanf("%lf%lf",&g[i].x,&g[i].y);
}
sort(g,g+n,cmp);
printf("%.2lf\n",fuc(0,n-1)/2);
}
return 0;
}
努力努力...