学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1007

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1107

 一样的题目，求一个最近点对。

求最近点对的方法，有很多。时间复杂度上有，n^2的，nlogn的，也有n的。

这里我用的是分治的那种方法。nlogn的方法。写的很挫，第一次写。慢慢优化。也没有精度判断。

Code：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 1e5 + 4;
const double INF = 1e100;
struct POINT
{
    double x, y;
}p[N], tmp[N];
int n;

double Distance(POINT a, POINT b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

bool cmpx(POINT a, POINT b)
{
    if(a.x < b.x) return true;
    else if(a.x == b.x && a.y < b.y) return true;
    return false;
}

bool cmpy(POINT a, POINT b)
{
    if(a.y < b.y) return true;
    else if(a.y == b.y && a.x < b.x) return true;
    return false;
}

double Near_Pair_Point(int l, int r)
{
    if(l == r) return INF;
    if(l + 1 == r) return Distance(p[l], p[r]);
    if(l + 2 == r) return min(Distance(p[l], p[l + 1]), min(Distance(p[l], p[r]), Distance(p[l + 1], p[r])));
    int mid = (l + r) / 2;
    double ans = min(Near_Pair_Point(l, mid), Near_Pair_Point(mid + 1, r));
    int top = 0;
    for(int i = mid; i >= l && p[mid].x - p[i].x <= ans; i --) tmp[top ++] = p[i];
    for(int i = mid + 1; i <= r && p[i].x - p[mid].x <= ans; i ++) tmp[top ++] = p[i];
    sort(tmp, tmp + top, cmpy);
    for(int i = 0; i < top - 1; i ++){
        for(int j = i + 1; j < top; j ++){
            if(Distance(tmp[i], tmp[j]) > ans) break;
            ans = min(ans, Distance(tmp[i], tmp[j]));
        }
    }
    return ans;
}

int main()
{
//    printf("%lf\n", INF);
//    freopen("1.txt", "r", stdin);
    while(scanf("%d", &n) && n){
        for(int i = 0; i < n; i ++){
            scanf("%lf %lf", &p[i].x, &p[i].y);
        }
        sort(p, p + n , cmpx);
        printf("%.2lf\n", Near_Pair_Point(0, n - 1) / 2.0);
    }
    return 0;
}

计算几何继续。。。。。。深搜，递归神马的太需要学习了。。。