KD-Tree
一开始看错题了aaarticlea/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDAAEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQH/2wBDAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQH/wAARCAAYABoDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD+u/8AbK/aO134M6JD4J8C+JfBngjx/rnw8+L3xl1T4ifEbQvEfirwD8H/ANnX4ES+BL39oD43674D8OazomufEe68GReP/BPhzwf8NdG17TpvE/jHxNo82ra3aeC7TxdPX5m6L+1bolzB8Srn4n/tf/8ABSr4SfFj4d+A/B/jmLwPqvwo/wCCfEmveM4viFqvwp8IeFfB/wAMvg98Pfgt8btEsfG2t+IfjT8GLHS/gr8abyx+NXhY/En4M6p4xMGm65H4wf6U/bd8CeLNW/a3+HGvaa8F9Yaz8Fr74cWdlDqxi1P+2b34p2+sm3vNIJ2jS9aC6JJ/aF0/lXV/pAjLCS0c18Uat4Y0HxLJ+21qPjz9nn9tP4123wXvfH/wBufix41/al/Yq8A2P7Pvw3+HHxR8P/HXwl4v+DdpZ698H/EngDTv7Z8D/CX48eDPF/i3wL448atpuj/Dd08S6ybLXfDbdlbLKOX5Lk+bzx8FVzuOOTwKlT/d4HB1asPr7lze9Kq4TUIqna0K0aspzXMfA5RxLLM+KuJMipZU/q/Dbypf2h/aHuzzPGzr1J4J5fGCX+w4GPOpLFJpzUuWUleX3d+wB+3xrXx4+K3xg/ZS+M+mahpfx0+DFi3iCCbW9M8B6Tq3xH+Gel+NLj4ceIvEOraN8NvjF8Y/A1j4w+GXxF0jV/h58TLfwZ8QNe8PWHjENo1xJoXxItPiF8KbH9ZtsP8Az7f+Rn/xr8Sv2dfCukwftT/s3fGTxJJ4rk+I/iX4IaAureKvizaeH0+McGkfEn4QaT4u1H4Y/EDXtC8N+FdE1K5XxNa+G72+i8N6Jonh1PGcTaTo3gi0lV5a/cHzZPRv++1/+JrfG5NWyOeFUcc8Rh8xy3BZjhpyS5lTruumuZcnMuaMmnZxakpQlODVR78H8U1OLKOeSw1NZZiMkz3H5HmGESjKMcXgZ8s3H2lRNXvdpd03GMm2/hPx5+zj4j+K/wC0tB4q8bWsqfDXw5beDtS0G60Lxj4i8M+IJte8OXU+uaPFBe+FNb0TXNLuNF8V21rq8phujpWpeH408LavFd6LdazpVer/ABH/AGPf2V/jT4+s/ib8WPgH8M/HvjCxg0S0HiLxR4R0nVJdSsdA1ObV/Dlv4itbiJ7XxPD4V1PF74cHiW0vRoupvJqmiQ2srzzEory8XmGJx9DAxruHLluAyvD4RU4cqhChicSoOV23Kbm3WnJ6zrSlOTblK/Rw3w9gMjqZ7PBzxUpZpnuPzrGSxFf2rnjMRODqJPkjy0FdKFF3SjGEXKUVI8N/ax+BmnXFjqPxJ8AeEdUvPHviXxp4d1DxLrOkz69qutXNlYeE7TwnZQW8DX14+gaFYf8ACP6Hu0jwxaWum2Wpvrvi2VE13UvHutzfYGj3+uvpGlvrjWdhrLadYtq9hb32nT29lqjWyHULSCczkzQ2115sMUpOZERXJJ3ZKK+hjj8TPJsswVSUatHBVcb9WVSCk6ca0MHKcI3dow5qalGEUoqUpys5Nt/HVMjwVDjLifH4eeJw9fNMBw5WxvsKqhCtWp/22o1XFU9JyUrSd2mlFJJpt//Z" alt="" />
其实是：给定n个点，从中找一个点，使得其他所有点到它距离的最大值与最小值之差最小。
利用KD-Tree暴力求出每个点的答案（找离它最近的点以及最远的点（当然只关心距离））
然后……两个过程分开写……
注意一下最近的点的距离不能是0（然而我一开始用 if (o==tmp) return INF; 就WA了……）（这里o是当前搜索到的点，tmp是枚举的起始点）
/**************************************************************
Problem: 1941
User: Tunix
Language: C++
Result: Accepted
Time:1484 ms
Memory:16900 kb
****************************************************************/ //BZOJ 1941
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=,INF=1e9;
/*******************template********************/ struct node{
int d[],mn[],mx[],l,r;
int& operator [] (int x){return d[x];}
void read(){d[]=getint(); d[]=getint();}
}t[N];
int n,m,D,root,tmp,ask_mx,ask_mn;
bool operator < (node a,node b){return a[D]<b[D];}
#define L t[o].l
#define R t[o].r
#define mid (l+r>>1)
void Push_up(int o){
F(i,,){
t[o].mn[i]=min(t[o].mn[i],min(t[L].mn[i],t[R].mn[i]));
t[o].mx[i]=max(t[o].mx[i],max(t[L].mx[i],t[R].mx[i]));
}
} int build(int l,int r,int dir){
D=dir;
nth_element(t+l,t+mid,t+r+);
int o=mid;
F(i,,) t[o].mn[i]=t[o].mx[i]=t[o][i];
if (l<mid) L=build(l,mid-,dir^);
if (mid<r) R=build(mid+,r,dir^);
Push_up(o);
return o;
} int dis(int a){return abs(t[a][]-t[tmp][])+abs(t[a][]-t[tmp][]);}
int calc_mn(int o){
if (!o) return INF;
int ans=;
F(i,,) ans+=max(,t[o].mn[i]-t[tmp][i]);
F(i,,) ans+=max(,t[tmp][i]-t[o].mx[i]);
return ans;
} void query_mn(int o){
if (!o) return;
int dl=calc_mn(L),dr=calc_mn(R),d0=dis(o);
if (d0) ask_mn=min(ask_mn,d0);
if (dl<dr){
if (dl<ask_mn) query_mn(L);
if (dr<ask_mn) query_mn(R);
}else{
if (dr<ask_mn) query_mn(R);
if (dl<ask_mn) query_mn(L);
}
} int calc_mx(int o){
if (!o) return -INF;
int ans=;
F(i,,) ans+=max(abs(t[o].mn[i]-t[tmp][i]),abs(t[o].mx[i]-t[tmp][i]));
return ans;
}
void query_mx(int o){
if (!o) return;
int dl=calc_mx(L),dr=calc_mx(R),d0=dis(o);
ask_mx=max(ask_mx,d0);
if (dl>dr){
if (dl>ask_mx) query_mx(L);
if (dr>ask_mx) query_mx(R);
}else{
if (dr>ask_mx) query_mx(R);
if (dl>ask_mx) query_mx(L);
}
} int main(){
#ifndef ONLINE_JUDGE
freopen("1941.in","r",stdin);
freopen("1941.out","w",stdout);
#endif
n=getint();
F(i,,n) t[i].read();
F(i,,) t[].mn[i]=INF,t[].mx[i]=-INF;
root=build(,n,);
int ans=INF;
F(i,,n){
ask_mn=INF; ask_mx=-INF;
tmp=i;
query_mn(root);
query_mx(root);
// printf("%d %d\n",ask_mx,ask_mn);
ans=min(ans,ask_mx-ask_mn);
}
printf("%d\n",ans);
return ;
}
1941: [Sdoi2010]Hide and Seek
Time Limit: 16 Sec Memory Limit: 162 MB
Submit: 385 Solved: 213
[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
0 0
1 0
0 1
1 1
Sample Output
HINT
对于30%的数据,N<=1000 对于100%的数据，N<=500000,0<=X,Y<=10^8 保证数据没有重点保证N>=2