先二分答案，转化为判断性问题。再将曼哈顿距离转化为切比雪夫距离。

考虑四个最外侧的点，只从他们开始连边，因为他们最容易满足边存在的条件。用并查集判断连通性。

复杂度nlog1e9，注意用long long

#include
     
      #include
      
       #include
       
        using namespace std;const int N=1e6+3;const int INF=0x7fffffff;typedef long long ll;int cur,un[N];int know(int u) {    return un[u]==u?u:un[u]=know(un[u]);}void connect(int l,int r){    l=know(l);    r=know(r);    if(l!=r)    {        cur--;        un[l]=r;    }}int n;ll x[N],y[N];int p1,p2,p3,p4;ll mnx,mny,mxx,mxy;bool check(ll d){    cur=n;    for(int i=1;i<=n;i++)        un[i]=i;    for(int i=1;i<=n;i++)    {        if(x[i]-x[p1]>=d)            connect(i,p1);        if(x[p2]-x[i]>=d)            connect(i,p2);        if(y[i]-y[p3]>=d)            connect(i,p3);        if(y[p4]-y[i]>=d)            connect(i,p4);    }    return cur==1;   }ll solve(){    ll l=0,r=max(mxx-mnx,mxy-mny),mid;    while(l