ABC 330 F Minimize Bounding Square

题意
给定xoy平面上的N个点，可以进行K次操作，每一次操作可以让这N个点中的一个点横向或纵向移动一个单位。最后用一个所有边都平行于x轴或y轴的正方形将这N个点包围，请最小化这个正方形的边长。

思路
最小化最大横向或纵向长度，显然二分答案。二分最后正方形的长度，现在问题转化为如何check。我们现在考虑一个问题，现在我们得到了最后的正方形边长mid，如果所有的点都被包含进去，那么我们将横向和纵向拆开了来看。以横向为例。所有的横向坐标都在一条长度为mid的线段里，那么我们先将x坐标排个序，然后定义left=1，right=N。那么我们每次将x[left]和x[right]组成一条线段，然后看这条线段的长度是否大于mid（正方形边长），如果大于那么多出的部分用k来抵消，如果小于或等于那么不管。同理，纵方向也是一样的操作，对于k的贡献是累加的。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+10;
const int mo=0;
int n,k,x[maxn],y[maxn];

bool check(int length)
{
	int res=0;
	int left=1;
	int right=n;
	while(left<right)
	{
		res+=max(x[right]-x[left]-length,mo)+max(y[right]-y[left]-length,mo);
		right--;
		left++;
	}
	return res<=k;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i]; 
	sort(x+1,x+1+n);
	sort(y+1,y+1+n);
	int l=0;
	int r=1e15;
	while(l<r)
	{
		int mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
	
	return 0;
}