「BZOJ1941」[SDOI2010] Hide and Seek
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
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
题解
自己yy了KDtree的模板。。。
枚举每个点找最近点，最远点更新答案
模板题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#include<cmath> #include<cstdio> #include<complex> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 1000000007 #define sqr(x) x*x using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int x[500005],y[500005]; int n,F,rt,ans=inf; struct P{ int d[2],mn[2],mx[2],l,r; int& operator[](int x){ return d[x]; } friend bool operator<(P a,P b){ return a[F]<b[F]; } friend int dis(P a,P b){ return abs(a[1]-b[1])+abs(a[0]-b[0]); } }p[500005]; struct kdtree{ P t[500005],T; int ans; void update(int k){ int l=t[k].l,r=t[k].r; for(int i=0;i<2;i++) { t[k].mn[i]=t[k].mx[i]=t[k][i]; if(l)t[k].mn[i]=min(t[k].mn[i],t[l].mn[i]); if(r)t[k].mn[i]=min(t[k].mn[i],t[r].mn[i]); if(l)t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]); if(r)t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]); } } int build(int l,int r,int now){ F=now; int mid=(l+r)>>1; nth_element(p+l,p+mid,p+r+1); t[mid]=p[mid]; for(int i=0;i<2;i++) t[mid].mn[i]=t[mid].mx[i]=t[mid][i]; if(l<mid)t[mid].l=build(l,mid-1,now^1); if(r>mid)t[mid].r=build(mid+1,r,now^1); update(mid); return mid; } int getmn(P a){ int ans=0; for(int i=0;i<2;i++) { ans+=max(T[i]-a.mx[i],0); ans+=max(a.mn[i]-T[i],0); } return ans; } int getmx(P a){ int ans=0; for(int i=0;i<2;i++) ans+=max(abs(T[i]-a.mx[i]),abs(T[i]-a.mn[i])); return ans; } void querymx(int k){ ans=max(ans,dis(t[k],T)); int l=t[k].l,r=t[k].r,dl=-inf,dr=-inf; if(l)dl=getmx(t[l]);if(r)dr=getmx(t[r]); if(dl>dr) { if(dl>ans)querymx(l); if(dr>ans)querymx(r); } else { if(dr>ans)querymx(r); if(dl>ans)querymx(l); } } void querymn(int k){ int tmp=dis(t[k],T); if(tmp)ans=min(ans,tmp); int l=t[k].l,r=t[k].r,dl=inf,dr=inf; if(l)dl=getmn(t[l]);if(r)dr=getmn(t[r]); if(dl<dr) { if(dl<ans)querymn(l); if(dr<ans)querymn(r); } else { if(dr<ans)querymn(r); if(dl<ans)querymn(l); } } int query(int f,int x,int y){ T[0]=x;T[1]=y; if(f==0)ans=inf,querymn(rt); else ans=-inf,querymx(rt); return ans; } }kdtree; int main() { n=read(); for(int i=1;i<=n;i++) { x[i]=read(),y[i]=read(); p[i][0]=x[i];p[i][1]=y[i]; } rt=kdtree.build(1,n,0); for(int i=1;i<=n;i++) { int mn=kdtree.query(0,x[i],y[i]),mx=kdtree.query(1,x[i],y[i]); ans=min(ans,mx-mn); } printf("%d\n",ans); return 0; } |
Subscribe
计数器 9863260
OI 课件=>
OI 课件=>