题意
给定$n$个二维坐标点,定义两个点之间的距离为$min(|x_1 - x_2|, |y_1 - y_2|)$,求所有点之间距离的最大值
分析
求最小值的最大值,显然用二分。二分的依据是存在两个点之间的距离大于等于$mid$。
- 如何判断一个点$i$能找到一个与它距离大于等于$mid$的点$j$?
因为距离的定义为横纵坐标差的较小值,因此$i$与$j$至少要满足横坐标之差大于等于$mid$,即保证$i$与$j$的$x$轴方向距离不小于$mid$,与此同时维护一个$maxv$和$minv$表示所有满足条件的$j$的纵坐标的最大值和最小值,只要存在maxv >= point[i].se + mid || minv <= point[i].se - mid
,就说明当前mid
成立,而且随着$i$的横坐标增大,满足条件的$j$的数量必然不会减少,因此可以利用双指针$O(n)$判断mid
的正确性.
// Problem: F - Dist Max 2
// Contest: AtCoder - AtCoder Beginner Contest 215
// URL: https://atcoder.jp/contests/abc215/tasks/abc215_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#define bug1(g) cout<<"test: "<<g<<endl
#define bug2(g , i) cout<<"test: "<<g<<" "<<i<<endl
#define bug3(g , i , k) cout<<"test: "<<g<<" "<<i<<" "<<k<<endl
#define bug4(a , g , i , k) cout<<"test: "<<a<<" "<<g<<" "<<i<<" "<<k<<endl
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define met(a , b) memset(a , b , sizeof a);
#define pb push_back
using namespace std;
template<class T> T chMa(T &a, T b) { return (a = max(a, b)); }
template<class T> T chMi(T &a, T b) { return (a = min(a, b)); }
typedef long long LL ;
typedef pair<int , int> PII;
const int N = 300010;
PII p[N];
void solve()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> p[i].fi >> p[i].se;
sort(p, p + n);
int l = 0, r = 1e9;
while (l < r)
{
int mid = l + r + 1 >> 1;
bool flag = false;
int maxv = -INF, minv = INF;
for (int i = 0, j = 0; i < n; i++)
{
while (j < i && p[j].fi <= p[i].fi - mid)
{
chMa(maxv, p[j].se);
chMi(minv, p[j].se);
j++;
}
if (maxv >= p[i].se + mid || minv <= p[i].se - mid)
{
flag = true;
break;
}
}
if (flag) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
int main()
{
ios::sync_with_stdio(0);
int T = 1;
// cin >> T;
for(int turn = 1 ; turn <= T ; turn++)
solve();
}