Submission #16712472

---

Source Code Expand

#include "bits/stdc++.h"
#include <bits/stdc++.h>

using namespace std;

// #define int long long

#ifndef bhupixb
    #define var(...)
    #define stl(...)
#endif

#define single_test

void solve() {
    int n;
    cin >> n;
    vector<pair<int,int>> v(n);
    for (auto &it: v) {
        cin >> it.first >> it.second;
    }
    int ans = 0;
    map<int,int> diff, add;
    for (auto [x, y]: v) {
        diff[x - y]++;
        add[x + y]++;
    }
    auto rem = [&] (int v, map<int,int> &mp) {
        int t = --mp[v];
        if (!t) mp.erase(v);
    };
    auto readd = [&] (int v, map<int,int> &mp) {
        mp[v]++;
    };
    for (auto [x, y]: v) {
        rem(x - y, diff);
        rem(x + y, add);

        if (!add.empty()) {
            int now = x + y;
            auto it = add.begin();
            ans = max(ans, now - it->first);
        }
        if (!diff.empty()) {
            int now = -x + y;
            auto it = prev(diff.end());
            ans = max(ans, now + it->first);
        }
        readd(x - y, diff);
        readd(x + y, add);
    }
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    #ifndef single_test
        cin >> t;
    #endif
    for (int i = 1; i <= t; ++i) {
        // cout << "Case #" << i << ": ";
        solve();
    }

    return 0;
}

Submission Info

Judge Result