結果

問題 No.2436 Min Diff Distance
コンテスト
ユーザー rniya
提出日時 2023-08-18 23:40:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 562 ms / 2,000 ms
コード長 2,958 bytes
コンパイル時間 2,638 ms
コンパイル使用メモリ 225,164 KB
最終ジャッジ日時 2025-02-16 10:59:58
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) 42
#endif

#define PII pair<int, int>
#define vec vector
#define str string
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define SZ(x) static_cast<int>((x).size())

using db = double;
using ll = long long;

struct DSU {
    vec<int> p;
    DSU(int _) : p(_ + 1) { iota(all(p), 0); }
    int f(int _) { return _ == p[_] ? _ : p[_] = f(p[_]); }
    bool same(int u, int v) { return f(u) == f(v); }
    bool unite(int u, int v) {
        u = f(u), v = f(v);
        if (u == v) return false;
        return p[u] = v, true;
    }
};

tuple<ll, vec<PII>> ManMST(vec<int> xs, vec<int> ys) {
    vec<int> id(SZ(xs));
    iota(all(id), 0);
    vec<tuple<ll, int, int>> edges;
    for (int s = 0; s < 2; s++) {
        for (int t = 0; t < 2; t++) {
            sort(all(id), [&](int i, int j) { return xs[i] + ys[i] < xs[j] + ys[j]; });
            map<int, int> sweep;
            for (int i : id) {
                for (auto it = sweep.lower_bound(-ys[i]); it != sweep.end(); it = sweep.erase(it)) {
                    int j = it->se;
                    if (xs[i] - xs[j] < ys[i] - ys[j]) break;
                    int w = abs(xs[i] - xs[j]) + abs(ys[i] - ys[j]);
                    edges.emplace_back(w, i, j);
                }
                sweep[-ys[i]] = i;
            }
            swap(xs, ys);
        }
        for (auto& x : xs) x = -x;
    }
    ll mst = 0;
    DSU dsu = DSU(SZ(xs));
    vec<PII> P;
    sort(all(edges));
    for (auto [w, u, v] : edges) {
        if (dsu.unite(u, v)) {
            mst += w, P.emplace_back(u, v);
        }
    }
    return {mst, P};
}

const int INF = (1 << 30) - 1;

void SingleTest(int TestCase) {
    int n;
    cin >> n;
    vec<int> xs(n), ys(n);
    for (int i = 0; i < n; i++) {
        cin >> xs[i] >> ys[i];
    }
    auto [mst, P] = ManMST(xs, ys);
    vector<vector<int>> v(n);
    for (auto [a, b] : P) {
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int max_x = -INF, min_x = INF, max_y = -INF, min_y = INF;
    for (int i = 0; i < n; i++) {
        int x = xs[i] + ys[i], y = xs[i] - ys[i];
        max_x = max(max_x, x);
        min_x = min(min_x, x);
        max_y = max(max_y, y);
        min_y = min(min_y, y);
    }
    int ans = INF;
    for (int i = 0; i < n; i++) {
        int mini = INF;
        for (int e : v[i]) {
            mini = min(mini, abs(xs[i] - xs[e]) + abs(ys[i] - ys[e]));
        }
        int x = xs[i] + ys[i], y = xs[i] - ys[i];
        int maxi = max({abs(max_x - x), abs(min_x - x), abs(max_y - y), abs(min_y - y)});
        ans = min(ans, maxi - mini);
    }
    cout << ans << '\n';
}

void init() {}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // cout << fixed << setprecision(10);
    int T = 1, TestCase = 0;
    // cin >> T;
    for (init(); T--;) SingleTest(++TestCase);
    return 0;
}
0