问题：

给定平面上N个点的坐标，找出距离最近的两个点。

 /*找出两边的最小值， 与中间点对可能形成的最小值找出最小值。除非是只剩下2个，三个点。否则在分治之后，每层都需要在递归回来之后归并处理。每层返回的最终ans都是该层的最小值，之后再返回给上一层*/

/*归并的时候首先把X方向上小于ans的点收集起来，再对Y方向上满足距离小于ans的点考察是否更小于ans*/

/*

ID: sdj22251

PROG: calfflac

LANG: C++

*/

#include <iostream>

#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <queue>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <string>

#include <cstring>

#include <cmath>

#include <ctime>

#define MAX 2000000000

#define LOCA

using namespace std;

struct node

{

    double x;

    double y;

    int id;

}p[200005],p1[100005],p2[100005];

bool cmp(node x, node y)

{

    return x.x < y.x;

}

double dist(node x, node y)

{

    if(x.id != y.id)

    return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));

    else return 2100000000.0; // id号相同肯定不行，直接返回一个很大的数

}

double Divide_conquer(int low, int high)

{

    if(high == low) return 2100000000.0; 

    if(high - low == 1) return dist(p[low], p[high]);

    int mid = (low + high) / 2;

    double d1 = Divide_conquer(low, mid);

    double d2 = Divide_conquer(mid + 1, high);

    double d = min(d1, d2);

int i, j, cnt1 = 0, cnt2 = 0;

 /*找出两边的最小值， 与中间点对可能形成的最小值找出最小值。除非是只剩下2个，三个点。否则在分治之后，每层都需要在递归回来之后归并处理。每层返回的最终ans都是该层的最小值，之后再返回给上一层*/

/*归并的时候首先把X方向上小于ans的点收集起来，再对Y方向上满足距离小于ans的点考察是否更小于ans*/

    for(i = mid; i >= low; i--)

    {

        if(p[mid].x - p[i].x < d)

        {

            p1[cnt1++] = p[i];

        }

    }

    for(i = mid + 1; i <= high; i++)

    {

        if(p[i].x - p[mid].x < d)

        {

            p1[cnt1++] = p[i];

        }

    }

sort(p1, p1 + cnt1-1, cmp2);

for(i=0;i<cnt1;i++)

for(j=i+1;j<=min(cnt1-1,i+8);j++)

d=min(d,dist(p1[i],p1[j]));

  /*  for(i = 0; i < cnt1; i++)

    {

        for(j = 0; j < cnt2; j++)

        {

            d = min(d, dist(p1[i], p2[j]));

        }

    }*/    return d;

}

int main()

{

#ifdef LOCAL

    freopen("calfflac.in","r",stdin);

    freopen("calfflac.out","w",stdout);

#endif

    int t, n, i, j;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%d", &n);

        for(i = 0; i < n; i++)

        {

            scanf("%lf%lf", &p[i].x, &p[i].y);

            p[i].id = 1;

        }

        for(i = n; i < 2 * n; i++)

        {

            scanf("%lf%lf", &p[i].x, &p[i].y);

            p[i].id = 2;

        }

        n = n * 2;

        sort(p, p + n, cmp);

        printf("%.3f\n", Divide_conquer(0, n - 1));

    }

return 0;

}

geometry3714