Manhattan MST

#include <bits/stdc++.h>

using std::vector;
using std::pair;
using std::tuple;

struct UnionFind {
    vector<int> par;
    UnionFind(const int n) : par(n, -1) {}
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (par[x] > par[y]) {
            std::swap(x, y);
        }
        par[x] += par[y];
        par[y] = x;
        return true;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i] >> Y[i];
    }
    vector<tuple<int, int, int>> edge;
    edge.reserve(4 * N);
    vector<int> idx(N);
    std::iota(idx.begin(), idx.end(), 0);
    for (int s = 0; s < 2; ++s) {
        for (int t = 0; t < 2; ++t) {
            std::sort(idx.begin(), idx.end(), [&](const int i, const int j) {
                return X[i] + Y[i] < X[j] + Y[j];
            });
            std::map<int, int, std::greater<>> map;
            for (const int i : idx) {
                for (auto itr = map.lower_bound(Y[i]); itr != map.end(); itr = map.erase(itr)) {
                    const int j = itr->second;
                    const int dx = X[i] - X[j];
                    const int dy = Y[i] - Y[j];
                    if (dy > dx) {
                        break;
                    }
                    edge.emplace_back(dx + dy, i, j);
                }
                map[Y[i]] = i;
            }
            std::swap(X, Y);
        }
        for (int i = 0; i < N; ++i) {
            X[i] *= -1;
        }
    }
    std::sort(edge.begin(), edge.end());
    UnionFind dsu(N);
    vector<pair<int, int>> used;
    used.reserve(N - 1);
    long long ans = 0;
    for (const auto& [c, i, j] : edge) {
        if (dsu.merge(i, j)) {
            ans += c;
            used.emplace_back(i, j);
        }
    }
    std::cout << ans << '\n';
    for (const auto& [i, j] : used) {
        std::cout << i << ' ' << j << '\n';
    }
    return 0;
}