题目链接：http://acm.swust.edu.cn/problem/794/
Time limit(ms): 1000 Memory limit(kb): 10000
Description
设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。
Input
多组测试数据，第一行为测试数据组数n（0<n≤100），每组测试数据由两个部分构成，第一部分为一个点的个数m（0<m≤1000），紧接着是m行，每行为一个点的坐标x和y，用空格隔开，（0<x，y≤100000）
Output
每组测试数据输出一行，为该组数据最近点的距离，保留4为小数。
Sample Input
2 2 0 0 0 1 3 0 0 1 1 1 0 |
Sample Output
1.0000 1.0000 |
Hint
algorithm textbook
不想多说，前几天写了一篇博客，主要讲的就是平面最近点对的问题，可以戳戳这里：http://www.cnblogs.com/zyxStar/p/4591897.html
直接上代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const double inf = 1e20;
const int maxn = ; struct Point{
double x, y;
}point[maxn]; int n, mpt[maxn], t; //以x为基准排序
bool cmpxy(const Point& a, const Point& b){
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
} bool cmpy(const int& a, const int& b){
return point[a].y < point[b].y;
} double min(double a, double b){
return a < b ? a : b;
} double dis(int i, int j){
return sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y));
} double Closest_Pair(int left, int right){
double d = inf;
if (left == right)
return d;
if (left + == right)
return dis(left, right);
int mid = (left + right) >> ;
double d1 = Closest_Pair(left, mid);
double d2 = Closest_Pair(mid + , right);
d = min(d1, d2);
int i, j, k = ;
//分离出宽度为d的区间
for (i = left; i <= right; i++){
if (fabs(point[mid].x - point[i].x) <= d)
mpt[k++] = i;
}
sort(mpt, mpt + k, cmpy);
//线性扫描
for (i = ; i < k; i++){
for (j = i + ; j < k && point[mpt[j]].y - point[mpt[i]].y<d; j++){
double d3 = dis(mpt[i], mpt[j]);
if (d > d3) d = d3;
}
}
return d;
} int main(){
scanf("%d", &t);
while (t--){
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%lf %lf", &point[i].x, &point[i].y);
sort(point, point + n, cmpxy);
printf("%.4lf\n", Closest_Pair(, n - ));
}
return ;
}