Gym 100959B Airports（Prim算法，曼哈顿距离变换，曼哈顿距离最大生成树）

今天训练遇到了这样一个题：给出平面上的n(1e5)个点，求d的最大值，使得所有距离不小于d的点连边后，图是联通的。
显然可以转化为求最大生成树的最小边权。
一种办法是优化边数，跑kruskal，这个网上有很多题解。
但是今天比赛的时候想了一种奇怪的做法，写完才发现好像和prim差不多：
我们维护两个集合A和B，一开始把随便一个点加入到A集合，其他的点都在B集合，然后重复以下操作：
找到分别属于集合A和集合B的最远点对，将对应B集合中的点加入A集合，直到所有点都在A集合中
过程中遇到的最小边权就是要找的d
然后受到暑假前一道题目的启发

在这个题里x1,y1,x2,y2都是变量，我们只需要用set分别维护集合A和B中x+y和x-y的值，对8种可能的情况取max，并把对应B集合中的点加到A集合中即可。
时间复杂度是O(nlogn)的。

//
// Created by vv123 on 2022/10/5.
//
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6 + 10, mod = 998244353;

struct point {
    int x, y, id;
} p[N];
class cmp1 {
public:
    bool operator()(const point& a, const point&b) const {
        if (a.x + a.y != b.x + b.y) return a.x + a.y < b.x + b.y;
        else return a.id < b.id;
    }
};
class cmp2 {
public:
    bool operator()(const point& a, const point&b) const {
        if (a.x - a.y != b.x - b.y) return a.x - a.y < b.x - b.y;
        else return a.id < b.id;
    }
};
int n;

int work() {
    int res = 1e18;
    set<point, cmp1> a1, b1;
    set<point, cmp2> a2, b2;
    a1.insert(p[1]); a2.insert(p[1]);
    for (int i = 2; i <= n; i++) {
        b1.insert(p[i]); b2.insert(p[i]);
    }
    for (int i = 2; i <= n; i++) {
        int mina1 = a1.begin()->x + a1.begin()->y;
        int maxa1 = a1.rbegin()->x + a1.rbegin()->y;
        int mina2 = a2.begin()->x - a2.begin()->y;
        int maxa2 = a2.rbegin()->x - a2.rbegin()->y;
        int minb1 = b1.begin()->x + b1.begin()->y;
        int maxb1 = b1.rbegin()->x + b1.rbegin()->y;
        int minb2 = b2.begin()->x - b2.begin()->y;
        int maxb2 = b2.rbegin()->x - b2.rbegin()->y;
        int mx1 = max({abs(mina1 - minb1), abs(mina1 - maxb1), abs(maxa1 - minb1), abs(maxa1 - maxb1)});
        int mx2 = max({abs(mina2 - minb2), abs(mina2 - maxb2), abs(maxa2 - minb2), abs(maxa2 - maxb2)});
        //if (max(mx1, mx2) < D) return false;
        int mx = max(mx1, mx2);
        res = min(res, mx);
        if (mx == mx1) {
            if (mx1 == abs(mina1 - minb1) || mx1 == abs(maxa1 - minb1)) {
                int id = b1.begin()->id;
                a1.insert(p[id]); a2.insert(p[id]);
                b1.erase(p[id]); b2.erase(p[id]);
            } else {
                int id = b1.rbegin()->id;
                a1.insert(p[id]); a2.insert(p[id]);
                b1.erase(p[id]); b2.erase(p[id]);
            }
        } else {
            if (mx2 == abs(mina2 - minb2) || mx2 == abs(maxa2 - minb2)) {
                int id = b2.begin()->id;
                a1.insert(p[id]); a2.insert(p[id]);
                b1.erase(p[id]); b2.erase(p[id]);
            } else {
                int id = b2.rbegin()->id;
                a1.insert(p[id]); a2.insert(p[id]);
                b1.erase(p[id]); b2.erase(p[id]);
            }
        }
    }
    return res;
}


signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
        p[i].id = i;
    }
    cout << work() << "\n";
    return 0;
}