算法思路分析

• 所有点按照横坐标从小到大排序
• 采用分治的思想进行做，每次比较两边的最小值，再比较中间的两边最小值
• 中间还有许多的细节需要处理

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int N = 100010;
const double INF = 1e15;
struct Seq
{
    int x, y;
    bool type; //标记类型，1为第一组，2为第二组
    bool operator <(const Seq&W)const
    {
        return x < W.x;
    }
}seq[N], temp[N];

double dist(Seq a, Seq b)
{
    if(a.type==b.type)return INF;

    double dx = a.x -b.x,dy = a.y -b.y;
    return sqrt(dx * dx+ dy * dy);
}

double dfs(int l, int r)
{
    if(l >= r)return INF; //不存在两个点返回正无穷
    int mid = l +r >> 1; //取出下一个要分界的点
    int mid_x = seq[mid].x; // 取出中间点的横坐标

    double res = INF;
    res = min(dfs(l, mid), dfs(mid + 1, r));// 取出两边点的最小值
    // 按照纵坐标 归并排序 
    {
        int k = 0, i = l, j = mid + 1;
        while(i <= mid && j <= r)
        {
            if(seq[i].y <= seq[j].y)temp[k ++] = seq[i ++];
            else temp[k ++]= seq[j ++];
        }

        while(i <= mid)temp[k ++] = seq[i ++];
        while(j <= r)temp[k ++] = seq[j ++];

        for(int i = l, x = 0;i <= r; i ++)
        seq[i] = temp[x ++];
    }
    // 取出所有在分界线两边 res范围内的点
    int k = 0;
    for(int i = l; i <= r; i ++)
        if(seq[i].x > mid_x - res && seq[i].x < mid_x + res)
            temp[k ++] = seq[i];
    // 经过分析可得每个点范围内的点数最多有6个因此该循环最坏6*n       
    for(int i =0; i < k; i ++)
        for(int j = i + 1;j <k && temp[j].y - temp[i].y < res; j ++)
            res = min(res, dist(temp[i], temp[j]));
    return res;
}

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int n;
        cin >>n;
        for(int i = 0; i < n; i ++)
        {
            int x, y;
            cin >> x >> y;
            seq[i] = {x, y, 0};
        }

        for(int i = 0; i < n; i++)
        {
            int x, y;
            cin >> x >>y;
            seq[i + n] = {x, y,1};
        }

        sort(seq, seq + n * 2); //所有点按照横坐标排序

        printf("%.3lf\n", dfs(0, 2 * n-1));// 分治
    }
    return 0;
}