Find the largest square without obstacles in a square of n*n. (n < = 1000, number of obstacles < = 10000)

It seems that it is a little difficult to enumerate. But if you think about it carefully, you can see that at least one side of the largest square is against the obstacle. So we just need to enumerate the largest square of each obstacle.

As for how to find the largest square in a certain direction, let's take the one on the right as an example. First, we preprocess the abscissa of all obstacles in each column and sort them. For the current obstacle in row X and column y, j pushes from column y+1 to the right, and updates l, r with the closest x abscissa in column y, and maxl and minr with l and r. the side length of the square is min (minr maxl, j-B [i]. Y). An optimization: when minr maxl is less than j-B [i]. Y, it can be deduced, because the resu lt of pushing further to the right is < = the current minr maxl.

Note: do not open the redundant array randomly. The space given by usaco training is only 16MB

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define inf 2147483647
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
using namespace std;

inline int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}

struct node{
	int x,y;
}b[10001];
int a[1001][1001];
vector<int> x[1001],y[1001];

inline bool cmp(node c,node d){
	return c.x<d.x;
}
inline bool cmp2(node c,node d){
	return c.y<d.y;
}

int main()
{
	freopen("bigbrn.in","r",stdin);
	freopen("bigbrn.out","w",stdout);
	int n=read(),m=read();
	for(int i=1;i<=m;++i) b[i].x=read(),b[i].y=read(),a[b[i].x][b[i].y]=1;
	sort(b+1,b+m+1,cmp);
	for(int i=1;i<=m;++i) x[b[i].y].pb(b[i].x);
	sort(b+1,b+m+1,cmp2);
	for(int i=1;i<=m;++i) y[b[i].x].pb(b[i].y);
	int ans=0;
	for(int i=1;i<=m;++i){
		int j=b[i].y+1,ml,mr;
		ml=0,mr=n+1;
		while(1){
			if(j>n) break;
			int pos,sz=x[j].size(),l,r;
			if(sz==0) l=1,r=n;
			else{
				pos=lower_bound(x[j].begin(),x[j].end(),b[i].x)-x[j].begin();
				if(pos==0) l=1,r=x[j][0]-1;
				else if(pos==sz) l=x[j][pos-1]+1,r=n;
				else l=x[j][pos-1]+1,r=x[j][pos]-1;
			}
			ml=max(ml,l);mr=min(mr,r);
			ans=max(ans,min(mr-ml+1,j-b[i].y));
			if(mr-ml+1<j-b[i].y) break;
			++j;
		}
		j=b[i].y-1;ml=0,mr=n+1;
		while(1){
			if(j<1) break;
			int pos,sz=x[j].size(),l,r;
			if(sz==0) l=1,r=n;
			else{
				pos=lower_bound(x[j].begin(),x[j].end(),b[i].x)-x[j].begin();
				if(pos==0) l=1,r=x[j][0]-1;
				else if(pos==sz) l=x[j][pos-1]+1,r=n;
				else l=x[j][pos-1]+1,r=x[j][pos]-1;
			}
			ml=max(ml,l);mr=min(mr,r);
			ans=max(ans,min(mr-ml+1,b[i].y-j));
			if(mr-ml+1<b[i].y-j) break;
			--j;
		}
		j=b[i].x+1;ml=0,mr=n+1;
		while(1){
			if(j>n) break;
			int pos,sz=y[j].size(),l,r;
			if(sz==0) l=1,r=n;
			else{
				pos=lower_bound(y[j].begin(),y[j].end(),b[i].y)-y[j].begin();
				if(pos==0) l=1,r=y[j][0]-1;
				else if(pos==sz) l=y[j][pos-1]+1,r=n;
				else l=y[j][pos-1]+1,r=y[j][pos]-1;
			}
			ml=max(ml,l);mr=min(mr,r);
			ans=max(ans,min(mr-ml+1,j-b[i].x));
			if(mr-ml+1<j-b[i].x) break;
			++j;
		}
		j=b[i].x-1;ml=0,mr=n+1;
		while(1){
			if(j<1) break;
			int pos,sz=y[j].size(),l,r;
			if(sz==0) l=1,r=n;
			else{
				pos=lower_bound(y[j].begin(),y[j].end(),b[i].y)-y[j].begin();
				if(pos==0) l=1,r=y[j][0]-1;
				else if(pos==sz) l=y[j][pos-1]+1,r=n;
				else l=y[j][pos-1]+1,r=y[j][pos]-1;
			}
			ml=max(ml,l);mr=min(mr,r);
			ans=max(ans,min(mr-ml+1,b[i].x-j));
			if(mr-ml+1<b[i].x-j) break;
			--j;
		}
	}
	printf("%d\n",ans);
	return 0; 
}