- BZOJ_1941_[Sdoi2010]Hide and Seek_KDtree
- 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
枚举一个点, 在 kdtree 中查离这个点最远的点和最近的点.
最元的点的估价就是横纵坐标最大的绝对值之和.
代码:
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- #define N 500050
- #define ls ch[p][0]
- #define rs ch[p][1]
- #define _max(x,y) ((x)>(y)?(x):(y))
- #define _min(x,y) ((x)<(y)?(x):(y))
- #define inf 0x3f3f3f3f
- int ch[N][2],mx[N][2],mn[N][2],now,ans1,ans2,n;
- struct Point {
- int p[2];
- bool operator <(const Point &x) const {
- return p[now]==x.p[now]?p[!now]<x.p[!now]:p[now]<x.p[now];
- }
- }a[N];
- inline char nc() {
- static char buf[100000],*p1,*p2;
- return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
- }
- int rd() {
- int x=0; char s=nc();
- while(s<'0'||s>'9') s=nc();
- while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();
- return x;
- }
- int Abs(int x) {return x>0?x:-x;}
- void pushup(int p,int x) {
- mx[p][0]=_max(mx[p][0],mx[x][0]);
- mn[p][0]=_min(mn[p][0],mn[x][0]);
- mx[p][1]=_max(mx[p][1],mx[x][1]);
- mn[p][1]=_min(mn[p][1],mn[x][1]);
- }
- int build(int l,int r,int type) {
- int mid=(l+r)>>1; now=type;
- nth_element(a+l,a+mid,a+r+1);
- mx[mid][0]=mn[mid][0]=a[mid].p[0];
- mx[mid][1]=mn[mid][1]=a[mid].p[1];
- if(l<mid) ch[mid][0]=build(l,mid-1,!type),pushup(mid,ch[mid][0]);
- if(r>mid) ch[mid][1]=build(mid+1,r,!type),pushup(mid,ch[mid][1]);
- return mid;
- }
- int dismin(int x,int y,int p) {
- return _max(mn[p][0]-x,0)+_max(x-mx[p][0],0)+_max(mn[p][1]-y,0)+_max(y-mx[p][1],0);
- }
- int dismax(int x,int y,int p) {
- return max(Abs(x-mx[p][0]),Abs(x-mn[p][0]))+max(Abs(y-mx[p][1]),Abs(y-mn[p][1]));
- }
- void query_min(int x,int y,int p) {
- int re=Abs(x-a[p].p[0])+Abs(y-a[p].p[1]),dl,dr;
- if(re&&re<ans1) ans1=re;
- dl=ls?dismin(x,y,ls):inf;
- dr=rs?dismin(x,y,rs):inf;
- if(dl<dr) {
- if(dl<ans1) query_min(x,y,ls);
- if(dr<ans1) query_min(x,y,rs);
- }else {
- if(dr<ans1) query_min(x,y,rs);
- if(dl<ans1) query_min(x,y,ls);
- }
- }
- void query_max(int x,int y,int p) {
- int re=Abs(x-a[p].p[0])+Abs(y-a[p].p[1]),dl,dr;
- if(re>ans2) ans2=re;
- dl=ls?dismax(x,y,ls):-inf;
- dr=rs?dismax(x,y,rs):-inf;
- if(dl>dr) {
- if(dl>ans2) query_max(x,y,ls);
- if(dr>ans2) query_max(x,y,rs);
- }else {
- if(dr>ans2) query_max(x,y,rs);
- if(dl>ans2) query_max(x,y,ls);
- }
- }
- int main() {
- n=rd();
- int i;
- for(i=1;i<=n;i++) a[i].p[0]=rd(),a[i].p[1]=rd();
- int root=build(1,n,0);
- int ans3=inf;
- for(i=1;i<=n;i++) ans1=inf,ans2=0,query_min(a[i].p[0],a[i].p[1],root),query_max(a[i].p[0],a[i].p[1],root),ans3=_min(ans3,ans2-ans1);
- printf("%d\n",ans3);
- }
- BZOJ_1941_[Sdoi2010]Hide and Seek_KDtree
来源: http://www.bubuko.com/infodetail-2676473.html