if(!vis[x-1][y])vis[x-1][y]=1,q[++tl]={x-1,y}; if(!vis[x][y+1])vis[x][y+1]=1,q[++tl]={x,y+1}; if(!vis[x][y-1])vis[x][y-1]=1,q[++tl]={x,y-1}; } return 0; } int dist(int a,int b,int c,int d){return (a-c)*(a-c)+(b-d)*(b-d);} int d[N][N],hd[N],len[N],s[N]; void add(point x){d[x.y][len[x.y]++]=x.x;} void del(point x){if(d[x.y][hd[x.y]]==x.x)hd[x.y]++;} void update(int y,int x){while(d[y][hd[y]+1]&&abs(d[y][hd[y]]-x)>=abs(d[y][hd[y]+1]-x))hd[y]++;} bool check(int x){ int dis=sqrt(x); mem(vis,0),mem(d,0),mem(hd,0),mem(len,0); for(int i=0;i<=max(n,m);i++)vis[0][i]=vis[i][0]=vis[n+1][i]=vis[i][m+1]=1; for(int i=1,l=1,r=1;i<=n;i++,mem(s,0)){ while(r<=num&&i+dis>=p[r].x)add(p[r++]); while(l<=num&&i-dis>p[l].x)del(p[l++]); for(int j=1;j<=m;j++){ update(j,i); int xx=d[j][hd[j]]; if(!xx)continue; int radius=sqrt(x-(xx-i)*(xx-i)),l=j-radius,r=j+radius+1; s[max(1,l)]++,s[min(m+1,r)]--; } for(int j=1;j<=m;j++)vis[i][j]=(s[j]+=s[j-1])>0; } return bfs(); } int main(){ cin>>n>>m>>stx>>sty>>edx>>edy>>num; for(int i=1;i<=num;i++)p[i].x=read(),p[i].y=read(),mp[p[i].x][p[i].y]=p[i]; for(int i=1,cnt=0;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j].x!=0)p[++cnt]=mp[i][j]; int l=-1,r=2e6; while(l>1)+1; check(m)?l=m:r=m-1; } cout<

题库

题库

367.[POI2006] ZAB-Frogs

提交记录

测试用例