chtholly-daisuki的小屋

「器用贫乏」

0%

abc215-f 题解

发表于 分类于 ， ，
一道有点难想的二分题[补题]

题目内容

vj题目链接洛谷

题目描述

在二维平面上给定 个互不相同的点。第 个点的坐标为 。

对于两个点 ，定义它们之间的距离为 ，即 坐标差和 坐标差中较小的一个。

请你求出所有不同的两点之间距离的最大值。

输入格式

输入以以下格式从标准输入读入。





输出格式

输出所有不同两点之间距离的最大值。

输入输出样例 #1

输入 #1

1
2
3
4
3
0 3
3 1
4 10

输出 #1

1
4

输入输出样例 #2

输入 #2

1
2
3
4
5
4
0 1
0 4
0 10
0 6

输出 #2

1
0

输入输出样例 #3

输入 #3

1
2
3
4
5
6
7
8
9
8
897 729
802 969
765 184
992 887
1 104
521 641
220 909
380 378

输出 #3

1
801

说明/提示

限制条件

  • 输入均为整数。

样例解释 1

点 和点 的距离为 ，点 和点 的距离为 ，点 和点 的距离为 。因此应输出 。

由 ChatGPT 4.1 翻译

思路

补题求最小的最大，一定要往二分答案去想

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
#define maxn 200010
#define MOD 998244353
#define lll long long
#define endl '\n'
int n;
struct point{
	int x,y;
}p[maxn];
bool cmp(point u,point v){
	return u.x<v.x;
}
int bfrmax[maxn],bfrmin[maxn];
bool check(int ans){//检测ans是否可行 ，允许复杂度：nlogn 
	//①线性递增的x的距离要大于一个值 -----l-----r-----
	//②若l的再左侧有一个lp，r的再右侧有rp
	//满足abs(lp.y-rp.y)>=x，则它们必然也满足①
	//此时即既满足delta(x)>ans，也满足delta(y)>ans 
	//cout<<ans<<endl;
	int rr=2;
	int premax=0,premin=1e9+10;
	for(int ll=1;ll<=n;ll++){//枚举left 
		//if(p[n].x-p[i].x>)
		premax=max(premax,p[ll].y);
		premin=min(premin,p[ll].y);
		for(rr;rr<=n+1;rr++){
			if(rr==n+1){
				//rr已到最右侧,所有可能的ll,rr都被枚举过
				//再也没有答案可供枚举了 
				return 0;
			}
			if(p[rr].x-p[ll].x>=ans){//找到了刚好满足的rr 
				break;
			}
		}
		if((premax-bfrmin[rr])>=ans||(bfrmax[rr]-premin)>=ans){
			return true;
		}
	}
	return false;
}
int main(){
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y;
	}
	sort(p+1,p+n+1,cmp);
	bfrmax[n+1]=0,bfrmin[n+1]=1e9+10;
	for(int i=n;i>=1;i--){
		bfrmax[i]=max(bfrmax[i+1],p[i].y);
		bfrmin[i]=min(bfrmin[i+1],p[i].y);
	}
	int l=0,r=1e9+10;
	while(l<r){//二分「答案」而不是x的下标i 
		int mid=(l+r+1)/2;
		//cout<<l<<":"<<mid<<":"<<r<<endl;
		if(check(mid)){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	cout<<l;
	return 0;
}