Star Code

对于平面上N个点，求其中两个距离最近的点。输入格式：点的个数N，然后是N个坐标即可计算出。

#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <stdlib.h>

struct pos {double x, y;};
typedef struct pos Pos;
Pos p[100000];
int d[100000];
double eps = 0.00001;

int cmp_x(const void *p, const void *q)
{
	double tmp=((Pos*)p)->x-((Pos*)q)->x;
	if(tmp>0) return 1;
	else if(fabs(tmp)<eps) return 0;
	else return -1;
}

double Dest(Pos p2, Pos p1)
{
    return ((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}

double Min(double a, double b)
{
    return a < b ? a : b;
}

int cmp(const void *a, const void *b)
{
     return(*(int *)a-*(int *)b);
}

double NSP(int left, int right)
{
    double m1, m2, m3 , res;
    int i, j, ix, mid;
    if(right - left == 1)
        return Dest(p[right], p[left]);
    else if(right - left == 2)
    {
        m1 = Dest(p[left], p[left+1]);
        m2 = Dest(p[left], p[left+2]);
        m3 = Dest(p[left+1], p[left+2]);
        return Min(m1, Min(m2, m3));
    }
    mid = (left+right)/2;
    res = Min(NSP(left, mid), NSP(mid+1, right));
    
    ix = 0;
    for(i = mid; i>=left && p[mid].x-p[i].x < res; --i)
        d[ix++] = i;
    for(i = mid+1; i<=right && p[i].x-p[mid+1].x < res; ++i)
        d[ix++] = i;
    qsort(d, ix, sizeof(d[0]), cmp);
    for(i = 0; i < ix; ++i)
        for(j = i+1; j<ix && j<i+4 && p[d[j]].y-p[d[i]].y < res; ++j)
            res = Min(res, Dest(p[d[j]], p[d[i]])); 
    return res;
}

int main(void)
{
    int N, i;
    while(scanf("%d", &N), N)
    {
    	assert(N!=1 && N<100000);
        for(i = 0; i < N; ++i)
            scanf("%lf %lf", &p[i].x, &p[i].y);
            
        qsort(p, N, sizeof(p[0]), cmp_x);
        printf("%.2lf\n", sqrt(NSP(0, N-1)));
    }
    return 0;
}

用的是分治法。