【hdoj 1007】最近点对

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <string>
#include <string.h>

#define MAXDIST 1000000

using namespace std;

struct Point{
    double x;
    double y;
};

int n;
double x, y;
bool tag;
Point tmp;
double eps = 1e-8;

Point gao[100005];

bool cmpxy (const Point a, const Point b)
{
    if(a.x != b.x)
    {
        return a.x < b.x;
    }
    else
    {
        return a.y < b.y;
    }
}

bool cmpx (const Point a, const Point b)
{
    return a.x < b.x;
}

bool cmpy (const Point a, const Point b)
{
    return a.y < b.y;
}

double dist(const Point a, const Point b)
{
    return ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double nearestPair(int head, int tail)
{
    if(head == tail)
    {
        return MAXDIST;
    }

    if(head + 1 == tail)
    {
        return dist(gao[head], gao[tail]);
    }

    int mid = (head + tail) >> 1;
    double d1 = nearestPair(head, mid);
    double d2 = nearestPair(mid + 1, tail);

    double mindist = d1 > d2 ? d2 : d1;

    for(int i = head; i<=tail; i++)
    {
        // 不能和自身比较，否则距离为 0
        if(i != mid && gao[i].x > (gao[mid].x - mindist) && gao[i].x < (gao[mid].x + mindist))
        {
            if(dist(gao[i], gao[mid]) < mindist)
                mindist = dist(gao[i], gao[mid]);
        }
    }

    return mindist;
}

int main()
{
    while(cin>>n && n!= 0)
    {
        memset(gao, 0, sizeof(gao));
        tag = false;

        for(int i=0; i<n; i++)
        {
            scanf("%lf%lf", &x, &y);
            tmp.x = x;
            tmp.y = y;
            gao[i] = tmp;
        }

        sort(gao, gao + n, cmpxy);
        for(int i=0; i < n-1; i++)
        {
            if(fabs(gao[i].x - gao[i+1].x) < eps && fabs(gao[i].y - gao[i+1].y) < eps)
                tag = true;
        }
        
        if(tag)
        {
            cout<<"0.00"<<endl;
            continue;
        }
        else
        {
            double d = nearestPair(0, n-1);
            printf("%.2f\n", sqrt(d)/2);
        }
    }
    return 0;
}