kdtree专题

自用笔记算法

kdtree专题

bzoj 2716&2648

题目要求

二维平面给出一些点
要求动态插入+动态询问
每次询问距离给定点最近点对的曼哈顿距离

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 200050
#define inf 0x3f3f3f3f 
using namespace std;
int n,m,root,cmp_d;
int k1,k2,k3,ans;
struct node{
   int d[2],l,r,Max[2],Min[2];
}t[maxn<<2],tmp;
inline bool cmp(node a,node b){
   return (a.d[cmp_d]<b.d[cmp_d]) || ((a.d[cmp_d]==b.d[cmp_d]) && (a.d[!cmp_d]<b.d[!cmp_d]));
}
void kd_updata(int p){
   if(t[p].l){
       if(t[p].Max[0]<t[t[p].l].Max[0]) t[p].Max[0]=t[t[p].l].Max[0];
       if(t[p].Min[0]>t[t[p].l].Min[0]) t[p].Min[0]=t[t[p].l].Min[0];
       if(t[p].Max[1]<t[t[p].l].Max[1]) t[p].Max[1]=t[t[p].l].Max[1];
       if(t[p].Min[1]>t[t[p].l].Min[1]) t[p].Min[1]=t[t[p].l].Min[1];
   }
   if(t[p].r){
       if(t[p].Max[0]<t[t[p].r].Max[0]) t[p].Max[0]=t[t[p].r].Max[0];
       if(t[p].Min[0]>t[t[p].r].Min[0]) t[p].Min[0]=t[t[p].r].Min[0];
       if(t[p].Max[1]<t[t[p].r].Max[1]) t[p].Max[1]=t[t[p].r].Max[1];
       if(t[p].Min[1]>t[t[p].r].Min[1]) t[p].Min[1]=t[t[p].r].Min[1];
   }
}
int kd_build(int l,int r,int D){
   int mid=(l+r)/2;
   cmp_d=D;
   nth_element(t+l+1,t+mid+1,t+r+1,cmp);
   t[mid].Max[0]=t[mid].Min[0]=t[mid].d[0];
   t[mid].Max[1]=t[mid].Min[1]=t[mid].d[1];
   if(l!=mid) t[mid].l=kd_build(l,mid-1,!D);
   if(r!=mid) t[mid].r=kd_build(mid+1,r,!D);
   kd_updata(mid);
   return mid;
}
inline void kd_insert(int now){
   int D,p;
   D=0;p=root;
   while(true){
       if(t[now].Max[0]>t[p].Max[0]) t[p].Max[0]=t[now].Max[0];
       if(t[now].Max[1]>t[p].Max[1]) t[p].Max[1]=t[now].Max[1];
       if(t[now].Min[0]<t[p].Min[0]) t[p].Min[0]=t[now].Min[0];
       if(t[now].Min[1]<t[p].Min[1]) t[p].Min[1]=t[now].Min[1];
       if(t[now].d[D]>=t[p].d[D]){
           if(t[p].r==0){
               t[p].r=now;
               return;
           }
           else p=t[p].r;
       }
       else{
           if(t[p].l==0){
               t[p].l=now;
               return;
           }
           else p=t[p].l;
       }
       D=!D;
   }
}
inline int dist(int p1,int px,int py){
   int dis=0;
   if(px<t[p1].Min[0]) dis+=t[p1].Min[0]-px;
   if(px>t[p1].Max[0]) dis+=px-t[p1].Max[0];
   if(py<t[p1].Min[1]) dis+=t[p1].Min[1]-py;
   if(py>t[p1].Max[1]) dis+=py-t[p1].Max[1];
   return dis;
}
inline void kd_ask(int p){
   int dl,dr,d0;
   d0=abs(t[p].d[0]-k2)+abs(t[p].d[1]-k3);
   if(d0<ans) ans=d0;
   if(t[p].l) dl=dist(t[p].l,k2,k3);
   else dl=inf;
   if(t[p].r) dr=dist(t[p].r,k2,k3);
   else dr=inf;
   if(dl<dr){
       if(dl<ans) kd_ask(t[p].l);
       if(dr<ans) kd_ask(t[p].r);
   }
   else{
       if(dr<ans) kd_ask(t[p].r);
       if(dl<ans) kd_ask(t[p].l);
   }
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d%d",&t[i].d[0],&t[i].d[1]);
	root=kd_build(1,n,0);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&k1,&k2,&k3);
		if(k1==1){
		   ++n;
		   t[n].Max[0]=t[n].Min[0]=t[n].d[0]=k2;
		   t[n].Max[1]=t[n].Min[1]=t[n].d[1]=k3;
		   kd_insert(n);
		}
		else{
		   ans=inf;
		   kd_ask(root);
		   printf("%d\n",ans);
		}
	}
}

思路

转跳链接
转跳链接

bzoj 3053 & HDU 4347

题目要求

给定n个维度为k的点
每次查询距离给定点最近的m个点
并按照距离从小到大排序m个点输出
这里的距离是欧几里德距离

参考AC代码

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
#include<bits/stdc++.h> 
#define maxn 50005  
#define inf 0x3f3f3f3f
using namespace std;   
struct arr{
	int d[5],max[15],min[15],l,r,id;  
	arr(){l=0;r=0;id=0;}  
}a[maxn<<2],aa[maxn];  
struct pop{
	double x;int id;  
	friend bool operator < (const pop &a,const pop &b){return a.x<b.x;}  
};  
priority_queue<pop>ans;  
int n,m,Q,t,x[15],D,temp[21],root,opt,P,flag;  
inline int cmp(arr a,arr b){
	return a.d[D]<b.d[D];  
}  
inline void up(int k,int s){ 
	for(int i=0;i<m;i++){
		a[k].min[i]=min(a[k].min[i],a[s].min[i]);  
		a[k].max[i]=max(a[k].max[i],a[s].max[i]);  
	}  
}  
int build(int l,int r,int dd){
	D=dd;int mid=((l+r)>>1);  
	nth_element(aa+l,aa+mid,aa+r+1,cmp);  
	for(int i=0;i<m;i++) a[mid].min[i]=a[mid].max[i]=a[mid].d[i]=aa[mid].d[i];  
	a[mid].id=mid;  
	if(l<mid) a[mid].l=build(l,mid-1,(dd+1)%m);else a[mid].l=0;  
	if(mid<r) a[mid].r=build(mid+1,r,(dd+1)%m);else a[mid].r=0;  
	if(a[mid].l) up(mid,a[mid].l);  
	if(a[mid].r) up(mid,a[mid].r);  
  	return mid;  
}  
inline double sdis(int k){
	double res=0;  
	for(int i=0;i<m;i++) res+=(a[k].d[i]-x[i])*(a[k].d[i]-x[i]);    
	return res;  
}  
void ask(int k,int deep){
	int L=a[k].l,R=a[k].r;  
	if (x[deep]>=a[k].d[deep]) swap(L,R);  
	double now=sdis(k);  
	if(L) ask(L,(deep+1)%m);  
	int flag=0;  
	if(ans.size()<P){
		ans.push((pop){now,k});
		flag=1;
	}  
	else{
		if(now<ans.top().x) ans.pop(),ans.push((pop){now,k});  
		if((x[deep]-a[k].d[deep])*1.*(x[deep]-a[k].d[deep])<ans.top().x) flag=1;  
	}  
	if(flag&&R) ask(R,(deep+1)%m);  
}  
int main(){ 
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF){ 
		for(int i=1;i<=n;i++){
			for(int j=0;j<m;j++) scanf("%d",&aa[i].d[j]);
		} 
		root=build(1,n,0);  
		scanf("%d",&Q);
		while(Q--){  
			for(int i=0;i<m;i++) scanf("%d",&x[i]);  
			scanf("%d",&P);
			ask(root,0);
			int wri=0;  
			printf("the closest %d points are:\n",P);  
			while(!ans.empty()){
				temp[++wri]=ans.top().id;  
				ans.pop();  
			}  
			for(int i=wri;i;i--){
				for(int j=0;j<m-1;j++) printf("%d ",a[temp[i]].d[j]);  
				printf("%d\n",a[temp[i]].d[m-1]);  
			}  
		}  
	}  
  return 0;  
}

思路

转跳链接

HDU 5992

题目要求

给出n个点 每个点有一个权值
m次询问
每次询问给出一个点和该点的权值w 询问距离该点最近且权值小于等于w的曼哈顿距离

参考AC代码

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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 205000;
const LL INF = 1e18;
struct point{
    int min, n, dot, l,r;
    LL d[2];
};
int n,m,root,now;
LL dis;
point t[MAXN];
point op,ans;
bool cmp_1(point a, point b){
    return a.d[now] < b.d[now];
}
void up_data(int rt){
    t[rt].min = t[rt].n;
    int l = t[rt].l, r = t[rt].r;
    if(l) t[rt].min=min(t[rt].min,t[l].min);
    if(r) t[rt].min=min(t[rt].min,t[r].min);
}
int build(int begin, int end, int fa,int fx){
    int m = (begin + end) >> 1;
    now = fx;
    nth_element(t + begin, t + m, t + end + 1, cmp_1);
    if(begin < m) t[m].l = build(begin, m - 1, m, 1 - fx);
    else t[m].l = 0;
    if(m < end) t[m].r = build(m + 1, end, m, 1 - fx);
    else t[m].r = 0;
    up_data(m);
    return m;
}
LL sqr(LL x){
    return x*x;
}
void query(int rt,int fx){
    if(!rt) return;
    int temp1 = t[rt].min;
    if(temp1 > op.n) return;
    if(t[rt].n <= op.n){
        LL dd = sqr(op.d[0]-t[rt].d[0])+sqr(op.d[1]-t[rt].d[1]);
        if(dd < dis || (dd==dis && t[rt].dot < ans.dot)){
            dis = dd;
            ans.d[0] = t[rt].d[0];
            ans.d[1] = t[rt].d[1];
            ans.n = t[rt].n;
            ans.dot = t[rt].dot;
        }
    }
    int zuo = t[rt].l,you = t[rt].r;
    if(op.d[fx]>t[rt].d[fx]) swap(zuo,you);
    query(zuo,1-fx);
    bool should = false;
    if(dis == INF) should = true;
    else{
        LL ju = sqr(op.d[fx]-t[rt].d[fx]);
        if (ju <= dis) should = true;
    }
    if(should) query(you,1-fx);
}
int main(){
//	freopen("input.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d", &n,&m);
    	for(int i = 1; i <= n; i++){
        	scanf("%I64d%I64d%d", &t[i].d[0], &t[i].d[1],&t[i].n);
        	t[i].dot = i;
    	}
        root = build(1, n, 0, 0);
	    for(int i = 1; i <= m; i++){
	        scanf("%I64d%I64d%d",&op.d[0],&op.d[1],&op.n);
	        dis = INF;
	        query(root,0);
	        printf("%I64d %I64d %d\n",ans.d[0],ans.d[1],ans.n);
	    }
    }
    return 0;
}

思路

转跳链接

HDU 2966

题目要求

给出n个点
对于每个点 输出距离他最近的曼哈顿距离

参考AC代码

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
#include<bits/stdc++.h>
using namespace std;  
typedef long long LL;  
typedef pair<int, int> PII;  
const int MX = 1e5 + 5;
struct Point{  
    int xy[2], l, r, id;  
    void read(int i) {  
        id = i;  
        scanf("%d%d", &xy[0], &xy[1]);  
    }  
}P[MX];  
int cmpw; LL ans;  
int idx[MX];  
bool cmp(const Point &a, const Point &b){  
    return a.xy[cmpw] < b.xy[cmpw];  
}  
int build(int l, int r, int w){  
    int m = (l + r) >> 1; cmpw = w;  
    nth_element(P + l, P + m, P + 1 + r, cmp);  
    idx[P[m].id] = m;  
    P[m].l = l != m ? build(l, m - 1, !w) : 0;  
    P[m].r = r != m ? build(m + 1, r, !w) : 0;  
    return m;  
}  
LL dist(LL x, LL y = 0){  
    return x * x + y * y;  
}  
void query(int rt, int w, LL x, LL y){  
    LL temp = dist(x - P[rt].xy[0], y - P[rt].xy[1]);  
    if(temp) ans = min(ans, temp);  
    if(P[rt].l && P[rt].r) {  
        bool sign = !w ? (x <= P[rt].xy[0]) : (y <= P[rt].xy[1]);  
        LL d = !w ? dist(x - P[rt].xy[0]) : dist(y - P[rt].xy[1]);  
        query(sign ? P[rt].l : P[rt].r, !w, x, y);  
        if(d < ans) query(sign ? P[rt].r : P[rt].l, !w, x, y);  
    } else if(P[rt].l) query(P[rt].l, !w, x, y);  
    else if(P[rt].r) query(P[rt].r, !w, x, y);  
}  
int main(){
//	freopen("input.txt","r",stdin);
    int T, n;
    scanf("%d", &T);  
    while(T--) {  
        scanf("%d", &n);  
        for(int i = 1; i <= n; i++) P[i].read(i);  
        int rt = build(1, n, 0);  
        for(int i = 1; i <= n; i++) {  
            ans = 1e18;  
            query(rt, 0, P[idx[i]].xy[0], P[idx[i]].xy[1]);  
            printf("%I64d\n", ans);  
        }  
    }  
    return 0;  
}

思路

kdtree模版题

hihocoder 1421(四叉树)

题目要求

n个点 m个询问
每次询问以某点为圆心 以r为半径的圆包含了多少个点

参考AC代码

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
#include<bits/stdc++.h> 
using namespace std;  
int xx[60000],yy[60000];  
struct node{  
    bool fafe;  
    int length,hao[5],x[2],y[2];  
    node * clidren[4];  
}pp[1000000];  
void lon(node *x){  
    x->length=0;  
    x->fafe=false;  
}  
int a,b,r,ans,lp,ll;  
void pan(int i){  
    if((a-xx[i])*(a-xx[i])+(b-yy[i])*(b-yy[i])<=r*r) ans++;  
}  
void add(int ii,node * x);  
void fen(node * x){  
    int mx=(x->x[0]+x->x[1])>>1;  
    int my=(x->y[0]+x->y[1])>>1;  
    for (int i=0;i<4;i++) x->clidren[i]=&pp[lp++];
    x->clidren[0]->x[0]=x->x[0];
	x->clidren[0]->x[1]=mx;  
    x->clidren[0]->y[0]=x->y[0];
	x->clidren[0]->y[1]=my;  
    x->clidren[1]->x[0]=mx+1;
	x->clidren[1]->x[1]=x->x[1];  
    x->clidren[1]->y[0]=x->y[0];
	x->clidren[1]->y[1]=my;  
    x->clidren[2]->x[0]=x->x[0];
	x->clidren[2]->x[1]=mx;  
    x->clidren[2]->y[0]=my+1;
	x->clidren[2]->y[1]=x->y[1];  
    x->clidren[3]->x[0]=mx+1;
	x->clidren[3]->x[1]=x->x[1];  
    x->clidren[3]->y[0]=my+1;
	x->clidren[3]->y[1]=x->y[1];  
    for(int i=0;i<4;i++) lon(x->clidren[i]);  
    for(int j=0;j< x->length ;j++){
        int ii=x->hao[j];  
        for(int i=0;i<4;i++){  
            if(x->clidren[i]->x[0]<=xx[ii]&&x->clidren[i]->x[1]>=xx[ii]&&x->clidren[i]->y[0]<=yy[ii]&&x->clidren[i]->y[1]>=yy[ii]){
                add(ii,x->clidren[i]);  
                break;  
            }  
        }  
    }  
    x->fafe=true;  
    x->length=0;  
}  
void add(int ii,node * x){
    if(!x->fafe){
        x->hao[x->length++]=ii;  
        if(x->length>ll) fen(x);   
    }  
    else{
        for(int i=0;i<4;i++){
            if (x->clidren[i]->x[0]<=xx[ii]&&x->clidren[i]->x[1]>=xx[ii]&&x->clidren[i]->y[0]<=yy[ii]&&x->clidren[i]->y[1]>=yy[ii]){ 
                add(ii,x->clidren[i]);   
                break;  
            }  
        }  
    }  
}  
void query(node * x,int l,int r,int xi,int s){
    if(!x->fafe){ 
        if(x->length){ 
            for (int i=0;i<x->length;i++)  
            pan(x->hao[i]);  
        }  
        return ;  
    }  
    for(int i=0;i<4;i++){  
        if(l>=x->clidren[i]->x[0]&&r<=x->clidren[i]->x[1]&&xi>=x->clidren[i]->y[0]&&s<=x->clidren[i]->y[1]){ 
            query(x->clidren[i],l,r,xi,s);  
            return ;  
        }  
    }  
    if(l>=x->clidren[1]->x[0]){
        query(x->clidren[1],l,r,xi,x->clidren[1]->y[1]);  
        query(x->clidren[3],l,r,x->clidren[3]->y[0],s);  
    }  
    else if(r<=x->clidren[0]->x[1]){
        query(x->clidren[0],l,r,xi,x->clidren[0]->y[1]);  
        query(x->clidren[2],l,r,x->clidren[2]->y[0],s);  
    }  
    else if (xi>=x->clidren[2]->y[0]){
        query(x->clidren[2],l,x->clidren[2]->x[1],xi,s);  
        query(x->clidren[3],x->clidren[3]->x[0],r,xi,s);  
    }  
    else if (s<=x->clidren[0]->y[1]){
        query(x->clidren[0],l,x->clidren[0]->x[1],xi,s);  
        query(x->clidren[1],x->clidren[1]->x[0],r,xi,s);  
    }  
    else{
        query(x->clidren[0],l,x->clidren[0]->x[1],xi,x->clidren[0]->y[1]);  
        query(x->clidren[1],x->clidren[1]->x[0],r,xi,x->clidren[1]->y[1]);  
        query(x->clidren[2],l,x->clidren[2]->x[1],x->clidren[2]->y[0],s);  
        query(x->clidren[3],x->clidren[3]->x[0],r,x->clidren[3]->y[0],s);  
    }  
}  
int main(){
//	freopen("input.txt","r",stdin);
    int n,m;  
    scanf("%d%d",&n,&m);  
    pp[0].x[0]=0; pp[0].x[1]=30000;  
    pp[0].y[0]=0; pp[0].y[1]=30000;  
    lon(&pp[0]);
	lp=1; ll=4;  
    for(int i=0;i<n;i++){
        scanf("%d%d",&xx[i],&yy[i]);  
        add(i,&pp[0]);  
    }  
    for(int i=0;i<m;i++){ 
        scanf("%d%d%d",&a,&b,&r);  
        ans=0;  
        query(&pp[0],max(0,a-r),min(30000,a+r),max(0,b-r),min(30000,b+r));  
        printf("%d\n",ans);  
    }  
    return 0;  
}

思路

四叉树实现

本文标题:kdtree专题

文章作者:Hippopmonkey

发布时间:2017-09-26, 15:58:21

最后更新:2017-09-26, 19:16:56

原始链接:http://xuboming8.github.io/2017/09/26/kdtree专题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. kdtree专题
    1. 1.1. bzoj 2716&2648
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. bzoj 3053 & HDU 4347
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 5992
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 2966
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. hihocoder 1421(四叉树)
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
|