问题

二维平面上的n个点，不存在完全重叠的两个点。请找出最接近的两个点之间的距离。

代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

struct point
{
    double x, y;
}p[100005];

int a[100005]; 

int cmpx(const point& a, const point& b)
{
    return a.x < b.x;
}
int cmpy(int& a, int& b)
{
    return p[a].y < p[b].y;
}
inline double dis(point& a, point& b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
inline double min(double a, double b)
{
    return a < b ? a : b;
}
double closest(int low, int high)
{
    if (low + 1 == high)
        return dis(p[low], p[high]);
    if (low + 2 == high)
        return min(dis(p[low], p[high]), min(dis(p[low], p[low + 1]), dis(p[low + 1], p[high])));
    int mid = (low + high) >> 1;
    double ans = min(closest(low, mid), closest(mid + 1, high)); 
    int i, j, cnt = 0;
    for (i = low; i <= high; ++i) 
    {
        if (p[i].x >= p[mid].x - ans && p[i].x <= p[mid].x + ans)
            a[cnt++] = i;      
    }
    sort(a, a + cnt, cmpy); 
    for (i = 0; i < cnt; ++i)
    {
        for (j = i + 1; j < cnt; ++j)
        {
            if (p[a[j]].y - p[a[i]].y >= ans)
                break;
            ans = min(ans, dis(p[a[i]], p[a[j]]));
        }
    }
    return ans;
}
int main(void)
{
    int i, n;
    while (scanf("%d", &n) != EOF)
    {
        if (!n)
            break;
        for (i = 0; i < n; ++i)
            scanf("%lf", &p[i].x);
        for (i = 0; i < n; ++i)
            scanf("%lf", &p[i].y);
        sort(p, p + n, cmpx);
        printf("%.4lf\n", closest(0, n - 1));
    }
    return 0;
}

样例

  最接近的点对为(90.46,8.07)和(91.64,38.22)，距离为30.1731。 对于30%的数据，n ≤1000， 对于100%的数据 n ≤50000，坐标值均 ≤100000 。

输入

• 第一行为一个正整数n。 第二行为n个数，表示n个点的横坐标。 第三行为n个数，表示n个点的纵坐标。

6
13.43 37.40 78.76 91.64 90.46 57.83
10.76 75.48 99.56 38.22 8.07 20.02

输出

• 最接近的两个点的欧式距离（保留四位有效小数）

30.1731