a已经按照x拍好了序的。。。
by BigJoker @ 2021-11-20 16:14:56
排
by BigJoker @ 2021-11-20 16:16:16
我也是这种写法，60pts，努力修改中……
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
const int N=2e4+10;
const int inf=1e10;
int n,vis[N],maxnx[4],maxny[4],minnx[4],minny[4];
struct node{
int x,y;
}a[N],b[N];
inline bool cmp1(node x,node y){
return x.x==y.x?x.y<y.y:x.x<y.x;
}
inline bool cmp2(node x,node y){
return x.y<y.y;
}
inline bool check(int maxn){
memset(vis,0,sizeof(vis));
queue<node>q[4];
int aim=0;
for(int i=0;i<=3;i++)maxnx[i]=maxny[i]=-inf,minnx[i]=minny[i]=inf;
++aim;
maxnx[1]=minnx[1]=a[1].x;maxny[1]=minny[1]=a[1].y;
for(int i=2;i<=n;i++){
int flag=0;
for(int j=1;j<=aim;j++){
if(a[i].x>=minnx[j]&&a[i].x<=minnx[j]+maxn){
if(a[i].y<minny[j]&&maxny[j]<=a[i].y+maxn)minny[j]=a[i].y,flag=j;
else if(a[i].y>=minny[j]&&a[i].y<=maxny[j])flag=j;
else if(a[i].y>maxny[j]&&minny[j]+maxn>=a[i].y)maxny[j]=a[i].y,flag=j;
}
if(flag){
maxnx[j]=max(maxnx[j],a[i].x);
break;
}
}
if(!flag)
++aim,maxnx[aim]=minnx[aim]=a[i].x,maxny[aim]=minny[aim]=a[i].y;
if(aim>3)return false;
}
/*if(maxn<=1){
cout<<"mid "<<maxn<<endl;
for(int i=1;i<=aim;i++)
cout<<minnx[i]<<" "<<maxnx[i]<<" "<<minny[i]<<" "<<maxny[i]<<endl;
cout<<endl;
}*/
return true;
}
signed main(){
IOS;
cin>>n;
int maxn=-inf,minn=inf;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
maxn=max(maxn,max(a[i].x,a[i].y));
minn=min(minn,min(a[i].x,a[i].y));
}
sort(a+1,a+n+1,cmp1);
int L=0,R=maxn-minn+1,mid,ans;
while(L<R){
mid=(L+R)>>1;
if(check(mid))ans=R=mid;
else L=mid+1;
}
cout<<ans;
return 0;
}
```
by 啷里个浪 @ 2021-12-05 16:49:29