给出数字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

/*
同bzoj热身赛,二维前缀和,灌水留坑
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int maxn = ,inf = ;
inline int read(){
char ch=getchar();
int f=,x=;
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
struct nd{
int x;
int y;
};
int p,n,m;
int ex[maxn],ey[maxn],xa,xb,ya,yb;
int flag,dis[][],vis[][];
short d[][],s[][];
int dx[] = {,,-,};
int dy[] = {,,,-};
bool emy[][];
inline bool jud(int x,int y,int t){
if(x < || y < || x >= m || y >= n) return false;
if(t == ) return true;
t--;
int tx=+x-y+t,ty=x+y+t,dx=+x-y-t,dy=x+y-t;
if(ty>=n+m-) ty = n+m-;
if(tx>=+m) tx = +m;
int tot = s[ty][tx];
if(dy>&&dx>-n) tot += s[dy-][dx-];
if(dy>) tot -= s[dy-][tx];
if(dx>-n) tot -= s[ty][dx-];
if(tot) return false;
else return true;
}
bool check(int t){
if(!jud(xa,ya,t)) return false;
flag++;
for(int i = ;i <= n+;i++){
for(int j = ;j <= m+;j++){
dis[i][j] = inf;
}
}
nd now,nxt;
now.x = xa;
now.y = ya;
queue<nd> q;
q.push(now);
dis[ya][xa] = ;
vis[ya][xa] = flag;
while(!q.empty()){
now = q.front();
q.pop();
//cout<<now.y<<" "<<now.x<<endl;
for(int dr = ;dr < ;dr++){
nxt.x = now.x + dx[dr];
nxt.y = now.y + dy[dr];
if(jud(nxt.x,nxt.y,t)&&vis[nxt.y][nxt.x] != flag){
dis[nxt.y][nxt.x] = dis[now.y][now.x] + ;
vis[nxt.y][nxt.x] = flag;
q.push(nxt);
if(nxt.y == yb && nxt.x == xb) return true;
}
}
}
return false;
}
int main(){
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
cin>>p>>m>>n>>xa>>ya>>xb>>yb;
for(int i = ;i <= p;i++){
scanf("%d%d",&ex[i],&ey[i]);
emy[ex[i]+ey[i]][+ex[i]-ey[i]] = true;
}
for(int i = ;i < n + m - ;i++){
for(int j = -n;j < +m;j++){
if(emy[i][j]) d[i][j] = d[i][j-] + ;
else d[i][j] = d[i][j-];
}
}
for(int i = ;i < n + m - ;i++){
for(int j = -n;j < +m;j++){
if(!i) s[i][j] = d[i][j];
else s[i][j] = s[i-][j] + d[i][j];
}
}
int l = ,r = n + m,mid,ans1,ans2;
while(l <= r){
mid = (l + r) >> ;
if(check(mid)){
ans1 = mid;
ans2 = dis[yb][xb];
l = mid + ;
}else{
r = mid - ;
}
}
cout<<ans1<<" "<<ans2;
return ;
}

最新文章

  1. XML带多属性解析为一个实体类(利用反射)
  2. oracle--导出、导入blob类型的字段
  3. Asp.Net Core 项目从 1.0.1 升级到 1.1.0 的小补丁
  4. Consistent hashing —— 一致性哈希
  5. JavaScript垃圾回收(三)——内存泄露
  6. 安装SQLSERVER2012遇到的一些问题
  7. 格式化日期的js(正则魅力)
  8. JSON-lib框架,JAVA对象与JSON、XML之间的相互转换
  9. highcharts 多数据+切换
  10. Mysql启动失败 MYSQL:The server quit without updating PID file
  11. 如何搞定前端资源服务跨域问题之nginx篇
  12. DevExpress GridControl一些属性使用方法总结
  13. SVN和GIT的使用
  14. WindowManager.LayoutParams的探究
  15. 使用VC建立网络连接并访问网络资源
  16. LeetCode--035--搜索插入位置(java)
  17. Python&#160;标准类库-数据类型之copy-深拷贝浅拷贝操作
  18. oldboy s21day02
  19. java应用健康检查
  20. 网络流Dinic模板

热门文章

  1. [NOIP2012] 普及组
  2. Redis未授权访问漏洞分析
  3. fabric note
  4. 偶然发现的Unity3d,两点之间的距离计算。
  5. persistent.xml hibernate 利用sql script 自定义生成 table 表
  6. phpexcel文本格式
  7. Runner之记计帐项目的典型用户和用户场景
  8. HTML学习笔记——锚链接、pre标签、实体
  9. 在64位系统上不能安装Matlab notebook的解决方案
  10. AJAX笔试面试题汇总