• 人类的智慧不是乱搞。
• 如果那些乱搞的人知道存在正解和乱搞代码一样短会如何感想？

——WeLikeStudying

本题解的思路源于大佬 WeLikeStudying 在题目《平面最近点对（加强加强版）》中发表的题解。

建议先简单阅读一下上面提到的这篇的题解并充分思考（最好完成）上面的这道模板题，因为接下来我们主要是对上面的这个做法进行补充并揭露其本质，以通过本题；而不是再详细叙述模板题的做法。

言归正传，我们简单过一下上面提到的这道模板题那位大佬是怎么做的：

首先，和暴力一样，考虑枚举每个点，算出到当前点到其他点的距离来不断最小化当前答案，枚举完后当前答案显然就是最终答案了。

先来思考一下为什么上面这个算法会 TLE，不难发现这是因为我们重复遍历了很多无用的状态。那我们不妨对遍历做一点限制：

• 枚举时只枚举横坐标不大于当前点的点，因为比当前点横坐标大的点在枚举到它的时候也会考虑用到当前点的距离来最小化答案。

不过这样剪枝后时间复杂度并没有发生变化，还是 $O\left(n^2\right)$。我们继续优化，发现和当前点的横坐标之差或纵坐标之差大于当前答案的点一定不会成功最小化当前答案（最优性剪枝），所以这些点也可以排除。

至此，我们考虑怎么实现这些剪枝。我们可以在枚举考虑每个点的同时维护一个集合，里面存有所有横坐标不大于当前点的，且所有横坐标与当前点的之差小于当前答案的点——也就是把第一个剪枝和第二个在横坐标方面的剪枝加进去了——然后再枚举集合中所有纵坐标与当前点的之差小于当前答案的点，分别计算到当前点的距离然后最小化当前答案即可。

显然这个集合可以用平衡树（std::set 即可胜任）维护。由于每次枚举到的点都是十分有限的（证明可以参考开头提到的题解），所以该算法的时间复杂度是 $O\left(n\log n\right)$。

对于本题，一个显然的想法是再加一对限制条件：枚举时只枚举特工，然后集合中只存电站。

但是请读者仔细思考，本题和那道模板题的区别在于：点的种类有两个——电站和特工，而这两种点各自之间是不能最小化答案的，所以第一个剪枝是不适用的。形象地说，模板题里枚举的点在枚举完了之后会成为接下来的枚举中会枚举到的点，所以在枚举当前点时不考虑横坐标比当前点的大的点不会影响算法的正确性；但是本题的特工在枚举完后在并不会被在将来枚举到的特工用来最小化答案，因为题目要求能被特工用来最小化答案的只有电站。

也就是说，本题到目前的问题就在于：对于某一个特工而言，到比它横坐标大的电站的距离并没有被用来最小化答案，造成了状态空间遍历得不完善。但是我们还不能放弃第一个剪枝，所以我们接下来要迎刃解决这个问题，而不是逃避这个问题。

一个简单的解决方法是：先用特工到横坐标不大于它的电站的距离最小化一遍当前答案，再用电站到横坐标不大于它的特工的距离最小化一遍当前答案。这样相当于让比某个特工的横坐标大的，且最近的一个电站更新了这个特工本来应该更新的答案，这是利用了两个子问题最优性的叠加。

因为只是比模板题多跑了一遍原算法，所以总时间复杂度仍为 $O\left(n\log n\right)$。参考代码如下：

#include <bits/stdc++.h>
using namespace std;

#define typeof(...) __decltype(__VA_ARGS__)
constexpr size_t MAXN = 1e5;

#ifndef _getchar_nolock
#define _getchar_nolock getchar_unlocked
#endif
class FastIn_Base {
public:
    template<typename _Ty>
    const FastIn_Base& operator>>(_Ty& __restrict__ int_var) const noexcept {
        int c; bool f;
        if (is_signed<_Ty>::value)
            f = false;
        while (!isdigit(c = _getchar_nolock()))
            if (is_signed<_Ty>::value && c == 45)
                f = true;

        int_var = c - 48;
        while (isdigit(c = _getchar_nolock()))
            int_var = int_var * 10 + (c - 48);

        if (is_signed<_Ty>::value && f)
            int_var = -int_var;
        return *this;
    }
};
#define cin ((FastIn_Base) {})

class Point {
public:
    uint32_t x, y;

    constexpr pair<uint32_t, uint32_t> get_pair(void) const noexcept {
        return make_pair(y, x);
    }

    constexpr bool operator<(const Point& __y) const noexcept {
        return x < __y.x;
    }
};

template<typename _Ty>
constexpr _Ty get_diff(const _Ty x, const _Ty y) noexcept {
    return x > y ? x - y : y - x;
}

template<typename _Ty>
bool to_min(_Ty& __restrict__ x, const _Ty y) noexcept {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

constexpr uint64_t sqr(const uint32_t x) noexcept {
    return (uint64_t)x * x;
}

constexpr uint64_t get_dist(const Point x, const Point y) noexcept {
    return sqr(get_diff(x.x, y.x)) + sqr(get_diff(x.y, y.y));
}

int main(void) noexcept {
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(3);

    uint16_t T;
    cin >> T;
    while (T--) {
        uint32_t N;
        cin >> N;
        Point station[MAXN], spy[MAXN];
        for (auto i = N; i--; cin >> station[i].x >> station[i].y);
        for (auto i = N; i--; cin >> spy[i].x >> spy[i].y);
        uint64_t ans = get_dist(station[0], spy[0]);
        sort(station, station + N);
        sort(spy, spy + N);
        {
            set<pair<uint32_t, uint32_t>> st;
            for (typeof(N)L = 0, R = 0, i = 0; i < N; ++i) {
                while (R < N && station[R].x <= spy[i].x)
                    st.insert(station[R++].get_pair());
                while (L < R && sqr(spy[i].x - station[L].x) >= ans)
                    st.erase(station[L++].get_pair());
                auto it = st.lower_bound(spy[i].get_pair());
                for (auto j = it; j != st.end() && sqr(j->first - spy[i].y) < ans; ++j)
                    to_min(ans, get_dist((Point) { j->second, j->first }, spy[i]));
                if (it != st.begin())
                    for (--it; sqr(spy[i].y - it->first) < ans; --it) {
                        to_min(ans, get_dist((Point) { it->second, it->first }, spy[i]));
                        if (it == st.begin())
                            break;
                    }
            }
        }
        set<pair<uint32_t, uint32_t>> st;
        for (typeof(N)L = 0, R = 0, i = 0; i < N; ++i) {
            while (R < N && spy[R].x <= station[i].x)
                st.insert(spy[R++].get_pair());
            while (L < R && sqr(station[i].x - spy[L].x) >= ans)
                st.erase(spy[L++].get_pair());
            auto it = st.lower_bound(station[i].get_pair());
            for (auto j = it; j != st.end() && sqr(j->first - station[i].y) < ans; ++j)
                to_min(ans, get_dist((Point) { j->second, j->first }, station[i]));
            if (it != st.begin())
                for (--it; sqr(station[i].y - it->first) < ans; --it) {
                    to_min(ans, get_dist((Point) { it->second, it->first }, station[i]));
                    if (it == st.begin())
                        break;
                }
        }
        cout << sqrtl(ans) << '\n';
    }
    return 0;
}

此代码在洛谷 Luogu 上是本题的最优解，同时也通过了所有我能找到的 hack 数据。