题目描述：

给你两个点集合，a集合，b集合。

求最近点对，要求一个点在a中，一个点在b中

解题报告：

最近点对的代码中只要限制所求的两个点一个来自a一个来自b，否则就是Max。

具体算法解释详见：

http://blog.sina.com.cn/s/blog_64675f540100lgqs.html

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define size 200000
#define Max 2000000000
struct pint{double x, y;bool flag;} jeo[size];
bool cmpx(const int &a, const int &b){return jeo[a].x < jeo[b].x;}
bool cmpy(const int &a, const int &b){return jeo[a].y < jeo[b].y;}
double dis(int &a, int &b)
{
    return sqrt((jeo[a].x - jeo[b].x) * (jeo[a].x - jeo[b].x) + (jeo[a].y - jeo[b].y) * (jeo[a].y - jeo[b].y));
}
int n, idx[size], idy[size];
bool same(int a, int b){return jeo[a].flag == jeo[b].flag;}
double judge(int l, int r)
{
    if (r - l == 1)
    {
        if (same(idx[l], idx[r])) return Max;
        else return dis(idx[l], idx[r]);
    }
    if (r - l == 2)
    {
        double tmp = Max;
        if (!same(idx[l], idx[l + 1])) tmp = min(tmp, dis(idx[l], idx[l + 1]));
        if (!same(idx[l + 1], idx[l + 2])) tmp = min(tmp, dis(idx[l + 1], idx[l + 2]));
        if (!same(idx[l + 2], idx[l])) tmp = min(tmp, dis(idx[l + 2], idx[l]));
        return tmp;
    }
    int mid = (l + r) >> 1;
    double ans = min(judge(l, mid), judge(mid + 1, r));
    int num = 0;
    for(int i = l; i <= r; i++)
        if (jeo[idx[i]].x >= jeo[idx[mid]].x - ans && jeo[idx[i]].x <= jeo[idx[mid]].x + ans)
            idy[num++] = idx[i];
    sort(idy, idy + num, cmpy);
    for(int i = 0; i < num; i++)
        for(int j = i + 1; j < num; j++)
        {
            if (!same(idy[i], idy[j]) && jeo[idy[j]].y - jeo[idy[i]].y >= ans) break;
            if (!same(idy[i], idy[j])) ans = min(ans, dis(idy[j], idy[i]));
        }
    return ans;
}
int main()
{
    int t;scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n + n; i++)
            scanf("%lf%lf", &jeo[i].x, &jeo[i].y), idx[i] = i, jeo[i].flag = (i < n);
        sort(idx, idx + n + n, cmpx);
        printf("%.3f\n", judge(0, n + n - 1));
    }
    return 0;
}