给出数字N（1<=N<=10000），X（1<=x<=1000），Y（1<=Y<=1000）,代表有N个敌人分布一个X行Y列的矩阵上，矩形的行号从0到X-1,列号从0到Y-1再给出四个数字x1,y1,x2,y2,代表你要从点(x1,y1)移到(x2,y2)。在移动的过程中你当然希望离敌人的距离的最小值最大化，现在请求出这个值最大可以为多少,以及在这个前提下，你最少要走多少步才可以回到目标点。注意这里距离的定义为两点的曼哈顿距离，即某两个点的坐标分为(a,b),(c,d),那么它们的距离为|a-c|+|b-d|。
输入：
第一行给出数字N，X，Y
第二行给出x1,y1,x2,y2
下面将有N行，给出N个敌人所在的坐标
输出：
在一行内输出你离敌人的距离及在这个距离的限制下，你回到目标点最少要移动多少步。
Sample input
2 5 6
0 0 4 0
2 1
2 3
Sample output
2 14
/* 先预处理出每个点与距离它最近的敌人的距离，然后二分+BFS 我的预处理貌似写麻烦了，但是比标程快一秒，嘿嘿…… */ #include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #define N 10010 #define M 1010 using namespace std; int dis[M][M],p,n,m,x1,y1,x2,y2; int qx[M*M],qy[M*M],step[M][M],vis[M][M],head,tail; int ax[4]={0,0,1,-1}; int ay[4]={1,-1,0,0}; struct node { int x,y; };node a[N]; bool check(int limit) { if(dis[x1][y1]<limit)return false; memset(step,0x3f3f3f3f,sizeof(step)); memset(vis,0,sizeof(vis)); head=0;tail=1; qx[1]=x1;qy[1]=y1;step[x1][y1]=0;vis[x1][y1]=1; while(head<tail) { ++head;int x=qx[head],y=qy[head]; if(x==x2&&y==y2)break; for(int i=0;i<4;i++) { int xx=x+ax[i],yy=y+ay[i]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&dis[xx][yy]>=limit) { ++tail; qx[tail]=xx; qy[tail]=yy; step[xx][yy]=step[x][y]+1; vis[xx][yy]=1; } } } if(step[x2][y2]<1000000000)return true; else return false; } void init() { memset(dis,0x3f3f3f3f,sizeof(dis)); for(int t=1;t<=p;t++) { int x=a[t].x,y=a[t].y; for(int i=x;i>=1;i--) { if(dis[i][y]<=abs(x-i))break; for(int j=y;j>=1;j--) { if(dis[i][j]<=(abs(x-i)+abs(y-j)))break; dis[i][j]=abs(x-i)+abs(y-j); } } for(int i=x+1;i<=n;i++) { if(dis[i][y]<=abs(x-i))break; for(int j=y;j>=1;j--) { if(dis[i][j]<=(abs(x-i)+abs(y-j)))break; dis[i][j]=abs(x-i)+abs(y-j); } } for(int i=x;i>=1;i--) { if(dis[i][y+1]<=abs(x-i))break; for(int j=y+1;j<=m;j++) { if(dis[i][j]<=(abs(x-i)+abs(y-j)))break; dis[i][j]=abs(x-i)+abs(y-j); } } for(int i=x+1;i<=n;i++) { if(dis[i][y+1]<=abs(x-i))break; for(int j=y+1;j<=m;j++) { if(dis[i][j]<=(abs(x-i)+abs(y-j)))break; dis[i][j]=abs(x-i)+abs(y-j); } } } } int main() { //freopen("jh.in","r",stdin); freopen("escape.in","r",stdin); freopen("escape.out","w",stdout); scanf("%d%d%d%d%d%d%d",&p,&n,&m,&x1,&y1,&x2,&y2); x1++;y1++;x2++;y2++; for(int i=1;i<=p;i++) { scanf("%d%d",&a[i].x,&a[i].y); a[i].x++;a[i].y++; } init(); int l=0,r=n*m,ans1,ans2; while(l<=r) { int mid=(l+r)/2; if(check(mid)) { ans1=mid; ans2=step[x2][y2]; l=mid+1; } else r=mid-1; } printf("%d %d",ans1,ans2); return 0; }