题意
长为(n)的线段上有(m)个点对((l,r)),两点间的距离为((r-l));现在可以修一个连接(x)和(y)的长度为0的通道,要求所有点对中最远距离的最小
思路
显然答案满足单调性,二分一个(mid),现在如果点对的距离已经(leq mid)就不考虑了;否则它们必须经过这条通道((x,y)),相当于对于所有这样的点对((l,r))都有(|x-l|+|y-r|leq mid)
将这个东西看做两点间的曼哈顿距离计算式;于是变成了判断一些中心点为((l,r))的斜了45度的正方形(对角线长度为(2 imes mid))是否有交集
通过将坐标旋转45度(即将坐标乘上矩阵(egin{bmatrix} 1 & 1 \ -1 & 1 end{bmatrix})),一个点((x,y))变成((x+y,y-x)),边的长度( imes sqrt{2})
于是正方形被拉正了,当成四条线求交集的范围就好了,见代码
代码还是很简单的
Code
#include<bits/stdc++.h>
#define N 100005
#define re register
#define Abs(x) ((x)>0?(x):(-(x)))
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
const int inf = 100000000;
int n,m,top;
struct Node { int x,y,d; } nd[N];
template <class T>
void read(T &x)
{
char c; int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
bool check(int mid)
{
int u=inf,d=-inf,l=-inf,r=inf;
for(int i=1;i<=m;++i)
{
if(nd[i].d<=mid) continue;
u=Min(u,nd[i].y+mid);
d=Max(d,nd[i].y-mid);
r=Min(r,nd[i].x+mid);
l=Max(l,nd[i].x-mid);
}
return (l<=r)&&(d<=u);
}
int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
read(n);read(m);
int l=0,r=n,ans=n;
for(re int i=1;i<=m;++i) read(nd[i].x) , read(nd[i].y) , nd[i].d=nd[i].y-nd[i].x;
for(re int i=1;i<=m;++i)
{
int x=nd[i].x,y=nd[i].y;
nd[i].x=y+x;
nd[i].y=y-x;
}
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<endl;
return 0;
}