注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1941][Sdoi2010]Hide and Seek  

2015-04-23 21:53:39|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1941: [Sdoi2010]Hide and Seek

Time Limit: 16 Sec  Memory Limit: 162 MB
Submit: 358  Solved: 199
[Submit][Status][Discuss]

Description

小猪iPig在PKU刚上完了无聊的猪性代数课,天资聪慧的iPig被这门对他来说无比简单的课弄得非常寂寞,为了消除寂寞感,他决定和他的好朋友giPi(鸡皮)玩一个更加寂寞的游戏---捉迷藏。 但是,他们觉得,玩普通的捉迷藏没什么意思,还是不够寂寞,于是,他们决定玩寂寞无比的螃蟹版捉迷藏,顾名思义,就是说他们在玩游戏的时候只能沿水平或垂直方向走。一番寂寞的剪刀石头布后,他们决定iPig去捉giPi。由于他们都很熟悉PKU的地形了,所以giPi只会躲在PKU内n个隐秘地点,显然iPig也只会在那n个地点内找giPi。游戏一开始,他们选定一个地点,iPig保持不动,然后giPi用30秒的时间逃离现场(显然,giPi不会呆在原地)。然后iPig会随机地去找giPi,直到找到为止。由于iPig很懒,所以他到总是走最短的路径,而且,他选择起始点不是随便选的,他想找一个地点,使得该地点到最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。 由于iPig现在手上没有电脑,所以不能编程解决这个如此简单的问题,所以他马上打了个电话,要求你帮他解决这个问题。iPig告诉了你PKU的n个隐秘地点的坐标,请你编程求出iPig的问题。

Input

第一行输入一个整数N 第2~N+1行,每行两个整数X,Y,表示第i个地点的坐标

Output

一个整数,为距离差的最小值。

Sample Input

4 0 0 1 0 0 1 1 1

Sample Output

1

HINT

对于30%的数据,N<=1000 对于100%的数据,N<=500000,0<=X,Y<=10^8 保证数据没有重点保证N>=2

Source

Solution

曼哈顿距离最大,估价为该点到平面域端点的最大距离(内部为0)
剩下的和上一篇差不多
感觉700B的直接求出最外面的菱形,对于每个点最远点对即可解决。最近点对的话,转坐标系,扫前后20个就可以了
不然kdtree怎么可能那么短!!!

Code

/**************************************************************
    Problem: 1941
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1028 ms
    Memory:21320 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
int n,x,y,i,dd,rt,amax,amin,aa,ans=1<<30;
struct T{int d[2],s[2],x[2],y[2];}t[1<<19];
struct P{int d[2];}a[1<<19];
bool operator<(const P&a,const P&b){return a.d[dd]<b.d[dd]||a.d[dd]==b.d[dd]&&a.d[dd^1]<b.d[dd^1];}
char B[1<<15],*S=B,*T=B,ch;
#define isd(c) (c>='0'&&c<='9')
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int F(){
    while(ch=getc(),!isd(ch));aa=ch-'0';
    while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return aa;
}
#define abs(x) (x>0?x:-(x))
#define max(a,b) (a>b?a:b)
#define cmax(a,b) (a<b?a=b:a)
#define cmin(a,b) (a>b?a=b:a)
#define ls t[now].s[0]
#define rs t[now].s[1]
#define mt(f,xx) cmin(t[f].x[0],t[xx].x[0]),cmax(t[f].x[1],t[xx].x[1]),cmin(t[f].y[0],t[xx].y[0]),cmax(t[f].y[1],t[xx].y[1])
int bt(int l,int r,int d){
    dd=d;int now=l+r>>1;
    std::nth_element(a+l,a+now,a+r+1);
    t[now].d[0]=t[now].x[0]=t[now].x[1]=a[now].d[0];
    t[now].d[1]=t[now].y[0]=t[now].y[1]=a[now].d[1];
    if(l<now)ls=bt(l,now-1,d^1),mt(now,ls);
    if(now<r)rs=bt(now+1,r,d^1),mt(now,rs);
    return now;
}
#define gmax(p) max(abs(x-t[p].x[1]),abs(t[p].x[0]-x))+max(abs(y-t[p].y[1]),abs(t[p].y[0]-y))
#define gmin(p) max(t[p].x[0]-x,0)+max(x-t[p].x[1],0)+max(t[p].y[0]-y,0)+max(y-t[p].y[1],0)
void qmax(int now){
    int d[2]={0,0},d0=abs(t[now].d[0]-x)+abs(t[now].d[1]-y),p;
    if(ls)d[0]=gmax(ls);if(rs)d[1]=gmax(rs);p=d[0]<=d[1];cmax(amax,d0);
    if(d[p]>amax)qmax(t[now].s[p]);
    if(d[p^1]>amax)qmax(t[now].s[p^1]);
}
void qmin(int now){
    int d[2]={1<<30,1<<30},d0=abs(t[now].d[0]-x)+abs(t[now].d[1]-y),p;
    if(ls)d[0]=gmin(ls);if(rs)d[1]=gmin(rs);p=d[0]>=d[1];if(d0)cmin(amin,d0);
    if(d[p]<amin)qmin(t[now].s[p]);
    if(d[p^1]<amin)qmin(t[now].s[p^1]);
}
int main(){
    for(n=F(),i=1;i<=n;i++)a[i]=(P){F(),F()};
    for(rt=bt(1,n,0),i=1;i<=n;i++){
        x=a[i].d[0],y=a[i].d[1];amax=0,amin=1<<30;
        qmax(rt),qmin(rt),cmin(ans,amax-amin);
    }
    printf("%d\n",ans);
}

  评论这张
 
阅读(72)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018