HDU 1007 平面最近点对（计算集几何）

http://acm.hdu.edu.cn/showproblem.php?pid=1007

我的代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define size 100000
struct pint{double x, y;} jeo[size];
bool cmpx(const int &a, const int &b){return jeo[a].x < jeo[b].x;}
bool cmpy(const int &a, const int &b){return jeo[a].y < jeo[b].y;}
double dis(int &a, int &b)
{
    return sqrt((jeo[a].x - jeo[b].x) * (jeo[a].x - jeo[b].x) + (jeo[a].y - jeo[b].y) * (jeo[a].y - jeo[b].y));
}
int n, idx[size], idy[size];
double judge(int l, int r)
{
    if (r - l == 1) return dis(idx[l], idx[r]);
    if (r - l == 2)
        return min(dis(idx[l], idx[l + 1]), min(dis(idx[l + 1], idx[l + 2]), dis(idx[l + 2], idx[l])));
    int mid = (l + r) >> 1;
    double ans = min(judge(l, mid), judge(mid + 1, r));
    int num = 0;
    for(int i = l; i <= r; i++)
        if (jeo[idx[i]].x >= jeo[idx[mid]].x - ans && jeo[idx[i]].x <= jeo[idx[mid]].x + ans)
            idy[num++] = idx[i];
    sort(idy, idy + num, cmpy);
    for(int i = 0; i < num; i++)
        for(int j = i + 1; j < num; j++)
        {
            if (jeo[idy[j]].y - jeo[idy[i]].y >= ans) break;
            ans = min(ans, dis(idy[j], idy[i]));
        }
    return ans;
}
int main()
{
    while(scanf("%d", &n) && n)
    {
        for(int i = 0; i < n && scanf("%lf%lf", &jeo[i].x, &jeo[i].y); i++)
            idx[i] = i;
        sort(idx, idx + n, cmpx);
        printf("%.2f\n", judge(0, n - 1) * 0.5);
    }
    return 0;
}

HDU 1007 平面最近点对（计算集几何）,布布扣,bubuko.com

HDU 1007 平面最近点对（计算集几何）

原文：http://blog.csdn.net/keshacookie/article/details/20065635