test/library_checker/geometry/manhattanmst.test.cpp

View this file on GitHub
Last update: 2024-11-18 03:54:10+09:00
Problem: https://judge.yosupo.jp/problem/manhattanmst

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/manhattanmst"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/graph/manhattanMST.hpp"

int main(){
    int n; cin >> n;
    vector<int> x(n), y(n);
    for(int i = 0; i < n; i++){
        cin >> x[i] >> y[i];
    }
    vector<pair<int, int>> ans = manhattanMST(x, y);
    long long sum = 0;
    for(auto [i, j] : ans){
        sum += abs(x[i] - x[j]) + abs(y[i] - y[j]);
    }
    cout << sum << "\n";
    for(auto [i, j] : ans){
        cout << i << " " << j << "\n";
    }
}

#line 1 "test/library_checker/geometry/manhattanmst.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/manhattanmst"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/graph/manhattanMST.hpp"

#line 2 "lib/data_structure/union_find.hpp"

/**
 * @brief Union-Find
 * @docs docs/data_structure/union_find.md
 */

#line 10 "lib/data_structure/union_find.hpp"

struct UnionFind{
    int V;
    std::vector<int> par;
    std::vector<int> edg;

    UnionFind(const int N) : V(N), par(N), edg(N){
        for(int i = 0; i < N; ++i){
            par[i] = -1;
            edg[i] = 0;
        }
    }

    int root(int x){
        assert(0 <= x && x < V);
        if(par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    int unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx == ry){
            edg[rx]++;
            return rx;
        }
        if(-par[rx] < -par[ry]) std::swap(rx, ry);
        par[rx] = par[rx] + par[ry];
        par[ry] = rx;
        edg[rx] += edg[ry] + 1;
        return rx;
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    long long size(int x){
        return -par[root(x)];
    }

    long long edge(int x){
        return edg[root(x)];
    }
};
#line 4 "lib/graph/manhattanMST.hpp"

/**
 * @brief Manhattan MST
 * @docs docs/graph/manhattanMST.md
 */

template <typename T>
vector<pair<int, int>> manhattanMST(vector<T> x, vector<T> y){
    int n = x.size();
    vector<tuple<T, int, int>> edge;
    edge.reserve(4 * n);
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    for(int s = 0; s < 2; ++s){
        for(int t = 0; t < 2; ++t){
            sort(idx.begin(), idx.end(), [&](const int i, const int j) {
                return x[i] + y[i] < x[j] + y[j];
            });
            map<T, int, greater<>> map;
            for(const int i : idx){
                for(auto iter = map.lower_bound(y[i]); iter != map.end(); iter = map.erase(iter)){
                    const int j = iter->second;
                    const T dx = x[i] - x[j];
                    const T dy = y[i] - y[j];
                    if(dy > dx) break;
                    edge.emplace_back(dx + dy, i, j);
                }
                map[y[i]] = i;
            }
            swap(x, y);
        }
        for(int i = 0; i < n; ++i) {
            x[i] *= -1;
        }
    }
    sort(edge.begin(), edge.end());
    UnionFind dsu(n);
    vector<pair<int, int>> used;
    used.reserve(n - 1);
    for(const auto &[c, i, j] : edge){
        if(!dsu.same(i, j)){
            used.emplace_back(i, j);
            dsu.unite(i, j);
        }
    }
    return used;
}
#line 6 "test/library_checker/geometry/manhattanmst.test.cpp"

int main(){
    int n; cin >> n;
    vector<int> x(n), y(n);
    for(int i = 0; i < n; i++){
        cin >> x[i] >> y[i];
    }
    vector<pair<int, int>> ans = manhattanMST(x, y);
    long long sum = 0;
    for(auto [i, j] : ans){
        sum += abs(x[i] - x[j]) + abs(y[i] - y[j]);
    }
    cout << sum << "\n";
    for(auto [i, j] : ans){
        cout << i << " " << j << "\n";
    }
}