KD-Tree 的模板题
- #include <bits/stdc++.h>
- #define ll long long
- #define inf 1e9+10
- #define eps 1e-7
- using namespace std;
- inline int read(){
- int x=0;int f=1;char ch=getchar();
- while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
- while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
- return x*f;
- }
- const int MAXN=1e6+10;
- struct node{
- int d[2],mn[2],mx[2],l,r;
- }p[MAXN<<1],T[MAXN<<1],t;
- int D,n,m,x[MAXN],y[MAXN],ans,root;
- inline bool operator < (node n,node m){
- return n.d[D]<m.d[D];
- }
- namespace KDTree{
- inline void update(int k){
- for(int i=0;i<=1;i++){
- if(T[k].l) T[k].mn[i]=min(T[T[k].l].mn[i],T[k].mn[i]),T[k].mx[i]=max(T[k].mx[i],T[T[k].l].mx[i]);
- if(T[k].r) T[k].mn[i]=min(T[T[k].r].mn[i],T[k].mn[i]),T[k].mx[i]=max(T[k].mx[i],T[T[k].r].mx[i]);
- }
- }
- inline int dis(node l){
- return abs(l.d[0]-t.d[0])+abs(l.d[1]-t.d[1]);
- }
- inline int build(int l,int r,int now){
- D=now;
- int mid=(l+r)>>1;
- nth_element(p+l,p+mid,p+r+1);
- T[mid]=p[mid];
- if(l<mid) T[mid].l=build(l,mid-1,now^1);
- if(r>mid) T[mid].r=build(mid+1,r,now^1);
- for(int i=0;i<=1;i++){
- T[mid].mn[i]=T[mid].mx[i]=T[mid].d[i];
- }
- update(mid);
- return mid;
- }
- inline int getmn(int k){
- int tmp=0;
- for(int i=0;i<=1;i++){
- tmp+=max(0,T[k].mn[i]-t.d[i]);
- tmp+=max(0,t.d[i]-T[k].mx[i]);
- }
- return tmp;
- }
- inline int getmx(int k){
- int tmp=0;
- for(int i=0;i<=1;i++){
- tmp+=max(abs(t.d[i]-T[k].mx[i]),abs(T[k].mn[i]-t.d[i]));
- }
- return tmp;
- }
- inline void querymn(int k){
- //cout<<k<<endl;
- //if(k==0) return;
- int tmp=dis(T[k]);
- if(tmp) ans=min(ans,tmp);
- int dl=inf,dr=inf;
- if(T[k].l) dl=getmn(T[k].l);
- if(T[k].r) dr=getmn(T[k].r);
- if(dl<dr){
- if(dl<ans) querymn(T[k].l);
- if(dr<ans) querymn(T[k].r);
- }
- else{
- if(dr<ans) querymn(T[k].r);
- if(dl<ans) querymn(T[k].l);
- }
- }
- inline void querymx(int k){
- ans=max(ans,dis(T[k]));
- int dl=-inf,dr=-inf;
- if(T[k].l) dl=getmx(T[k].l);
- if(T[k].r) dr=getmx(T[k].r);
- if(dl>dr){
- if(dl>ans) querymx(T[k].l);
- if(dr>ans) querymx(T[k].r);
- }
- else{
- if(dr>ans) querymx(T[k].r);
- if(dl>ans) querymx(T[k].l);
- }
- }
- inline int query(int f,int x,int y){
- t.d[0]=x;t.d[1]=y;
- if(f==0) ans=inf,querymn(root);
- else ans=-inf,querymx(root);
- return ans;
- }
- void init(){
- n=read();
- for(int i=1;i<=n;i++){
- p[i].d[0]=x[i]=read();p[i].d[1]=y[i]=read();
- }
- root=build(1,n,0);
- }
- void solve(){
- int mnn=inf;
- for(int i=1;i<=n;i++){
- int mn=query(0,x[i],y[i]);
- int mx=query(1,x[i],y[i]);
- mnn=min(mnn,mx-mn);
- }
- cout<<mnn<<endl;
- }
- }
- int main(){
- //freopen("All.in","r",stdin);
- //freopen("ba.out","w",stdout);
- using namespace KDTree;
- init();
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2450014.html