当前位置：首页 > news >正文

F - Dist Max 2

news 2025/11/24 10:27:11

// 特别是二分的验证。。
// 两个维度第一个维度用滑窗来控制|x1-x2|>=k
// 第二个维度只需要迭代mx 和mi 。。最远距离一定出现在这两个端点之一。。

// 这是一个我感觉挺特别的二维。。维护的数据。。。问题。。。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128_t
#define ar array<int, 2>
#define arr array<int, 3>
int  n, m, k, inf = 1LL << 61, mod = 998244353;// 1e9+7;
const int N = 5e5 + 50;void solve() {cin >> n;ar a[n];for (auto&[x, y] : a)cin >> x >> y;sort(a, a + n);auto ok = [&](int k) {int mx = -inf, mi = inf;int i = 0;for (auto[x, y] : a) {while (i < n && a[i][0] + k <= x) {mi = min(mi, a[i][1]);mx = max(mx, a[i][1]);i++;}if (y - mi >= k || mx - y >= k) {return 1;}}return 0;};int l = 0, r = inf;while (l < r) {int mid = (l + r + 1) >> 1;if (ok(mid))l = mid;elser = mid - 1;}cout << l;
};signed main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);
#ifdef DEBUGfreopen("../1.in", "r", stdin);
#endif//init_f();//init();//expr();// int T; cin >> T; while(T--)solve();return 0;
}