Reku
0%

kd树练习:最近距离查询

Posted on Edited on In Views: Valine:

k-d就是k个维度，k-d树其实就是用不同的维度来对点集进行划分，从而达到快速查找的目的。 时间复杂度比较科学的方法，一般是算出点集在某个维度上的方差，然后选择方差最大的维度，对点集进行划分，但是由于涉及到double的运算，有时在时间复杂度上并不尽如人意。所以轮换维度进行分割的方法也比较常见。 k-d树最简单的应用，就是查询在一个点集中，离一个点最近的点是哪个。 其实就是设定一个距离，然后不断的查找k-d树的子树，以查询点为圆心的圆会随着查询，逐渐的缩小。 这个查询的最差时间复杂度是\(O(\sqrt n)\)，平均的时间复杂度大概是\(O(log(n))\)。 http://acm.hdu.edu.cn/showproblem.php?pid=2966 裸的kd树，求每个点到点集的最近点

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
#include<bits/stdc++.h>

#define INT_INF 0x3fffffff
#define LL_INF 0x3fffffffffffffff
#define EPS 1e-12
#define MOD 1000000007
#define PI 3.141592653579798
#define N 600000

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;

struct data
{
    LL pos[10];
    int id;
} T[N] , op , point;
data W[N];
int split[N],now,n,demension;

bool use[N];
LL ans,id;
DB var[10];

bool cmp(data a,data b)
{
    return a.pos[split[now]]<b.pos[split[now]];
}

void build(int L,int R)
{
    if(L>R) return;

    int mid=(L+R)>>1;
    
    for(int pos=0;pos<demension;pos++)
    {
        DB ave=var[pos]=0.0;
        for(int i=L;i<=R;i++)
            ave+=T[i].pos[pos];
        ave/=(R-L+1);
        for(int i=L;i<=R;i++)
            var[pos]+=(T[i].pos[pos]-ave)*(T[i].pos[pos]-ave);
        var[pos]/=(R-L+1);
    }
    
    split[now=mid]=0;
    for(int i=1;i<demension;i++)
        if(var[split[mid]]<var[i]) split[mid]=i;
    
    nth_element(T+L,T+mid,T+R+1,cmp);
    
    build(L,mid-1);
    build(mid+1,R);
}

void query(int L,int R)
{
    if(L>R) return;
    int mid=(L+R)>>1;
    
    LL dis=0;
    for(int i=0;i<demension;i++)
        dis+=(op.pos[i]-T[mid].pos[i])*(op.pos[i]-T[mid].pos[i]);
    
    if(!use[T[mid].id] && dis<ans)
    {
        ans=dis;
        point=T[mid];  
        id=T[mid].id;  
    }
    
   
    LL radius=(op.pos[split[mid]]-T[mid].pos[split[mid]])*(op.pos[split[mid]]-T[mid].pos[split[mid]]);
    
    if(op.pos[split[mid]]<T[mid].pos[split[mid]])
    {
        query(L,mid-1);
        if(radius<=ans) query(mid+1,R);
    }
    else
    {
        query(mid+1,R);
        if(radius<=ans) query(L,mid-1);
    }
}

void work()
{
    scanf("%d",&n);
    demension=2;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<demension;j++)
            scanf("%lld",&T[i].pos[j]);
        T[i].id=i;
        W[i]=T[i];
    }
    
    build(1,n);  

    int m,q;
    for(int q=1;q<=n;q++)
    {
        op=W[q];
        use[q]=1;
        ans=(((LL)INT_INF)*INT_INF);
        query(1,n);
        use[q]=0;
        printf("%lld\n",ans);
    }
    return;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--) work();
    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=4347 裸，求最近的m个点

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
#include<bits/stdc++.h>

#define INT_INF 0x3fffffff
#define LL_INF 0x3fffffffffffffff
#define EPS 1e-12
#define MOD 1000000007
#define PI 3.141592653579798
#define N 60000

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;

struct data
{
    LL pos[10];
    int id;
} T[N] , op , point;
int split[N],now,n,demension;

bool use[N];
LL ans,id;
DB var[10];

bool cmp(data a,data b)
{
    return a.pos[split[now]]<b.pos[split[now]];
}

void build(int L,int R)
{
    if(L>R) return;

    int mid=(L+R)>>1;
    
    for(int pos=0;pos<demension;pos++)
    {
        DB ave=var[pos]=0.0;
        for(int i=L;i<=R;i++)
            ave+=T[i].pos[pos];
        ave/=(R-L+1);
        for(int i=L;i<=R;i++)
            var[pos]+=(T[i].pos[pos]-ave)*(T[i].pos[pos]-ave);
        var[pos]/=(R-L+1);
    }
    
    split[now=mid]=0;
    for(int i=1;i<demension;i++)
        if(var[split[mid]]<var[i]) split[mid]=i;
    
    nth_element(T+L,T+mid,T+R+1,cmp);
    
    build(L,mid-1);
    build(mid+1,R);
}

void query(int L,int R)
{
    if(L>R) return;
    int mid=(L+R)>>1;
    
    LL dis=0;
    for(int i=0;i<demension;i++)
        dis+=(op.pos[i]-T[mid].pos[i])*(op.pos[i]-T[mid].pos[i]);
    
    if(!use[T[mid].id] && dis<ans)
    {
        ans=dis;
        point=T[mid];
        id=T[mid].id;
    }
    
    LL radius=(op.pos[split[mid]]-T[mid].pos[split[mid]])*(op.pos[split[mid]]-T[mid].pos[split[mid]]);
    
    if(op.pos[split[mid]]<T[mid].pos[split[mid]])
    {
        query(L,mid-1);
        if(radius<=ans) query(mid+1,R);
    }
    else
    {
        query(mid+1,R);
        if(radius<=ans) query(L,mid-1);
    }
}

int main()
{
    while(scanf("%d%d",&n,&demension)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<demension;j++)
                scanf("%I64d",&T[i].pos[j]);
            T[i].id=i;
        }
        
        build(1,n);

        int m,q; scanf("%d",&q);
        while(q--)
        {
            memset(use,0,sizeof(use));
            
            for(int i=0;i<demension;i++)
                scanf("%I64d",&op.pos[i]);
            scanf("%d",&m);
            printf("the closest %d points are:\n",m);
            while(m--)
            {
                ans=(((LL)INT_INF)*INT_INF);
                query(1,n);
                for(int i=0;i<demension;i++)
                {
                    printf("%I64d",point.pos[i]);
                    if(i==demension-1) printf("\n");
                    else printf(" ");
                }
                use[id]=1;
            }
        }
    }
    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=5992 今年青岛的原题，确实很裸。

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include<bits/stdc++.h>

#define INT_INF 0x3fffffff
#define LL_INF 0x3fffffffffffffff
#define EPS 1e-12
#define MOD 1000000007
#define PI 3.141592653579798
#define N 200010
#define mk make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;

struct data
{
    LL pos[10];
    int id;
    LL c;
} T[N] , op , point;
int split[N],now,n,demension;
data W[N];
bool use[N];
LL ans,id;
DB var[10];

bool cmp(data a,data b)
{
    return a.pos[split[now]]<b.pos[split[now]];
}

void build(int L,int R)
{
    if(L>R) return;

    int mid=(L+R)>>1;
    
    for(int pos=0;pos<demension;pos++)
    {
        DB ave=var[pos]=0.0;
        for(int i=L;i<=R;i++)
            ave+=T[i].pos[pos];
        ave/=(R-L+1);
        for(int i=L;i<=R;i++)
            var[pos]+=(T[i].pos[pos]-ave)*(T[i].pos[pos]-ave);
        var[pos]/=(R-L+1);
    }
    
    split[now=mid]=0;
    for(int i=1;i<demension;i++)
        if(var[split[mid]]<var[i]) split[mid]=i;
    
    nth_element(T+L,T+mid,T+R+1,cmp);
    
    build(L,mid-1);
    build(mid+1,R);
}

void query(int L,int R)
{
    if(L>R) return;
    int mid=(L+R)>>1;
    
    LL dis=0;
    for(int i=0;i<demension;i++)
        dis+=(op.pos[i]-T[mid].pos[i])*(op.pos[i]-T[mid].pos[i]);
    
    if(!use[T[mid].id] && dis<ans)
    {
        ans=dis;
        point=T[mid];  
        id=T[mid].id;  
    }
    else if(!use[T[mid].id] && dis==ans && id>T[mid].id)
    {
        point=T[mid];  
        id=T[mid].id;  
    }
    LL radius=(op.pos[split[mid]]-T[mid].pos[split[mid]])*(op.pos[split[mid]]-T[mid].pos[split[mid]]);
    
    if(op.pos[split[mid]]<T[mid].pos[split[mid]])
    {
        query(L,mid-1);
        if(radius<=ans) query(mid+1,R);
    }
    else
    {
        query(mid+1,R);
        if(radius<=ans) query(L,mid-1);
    }
}
vector<pair<LL,int> > pp;
data an[N];
bool cmp1(data a,data b)
{
    return a.c>b.c;
}
bool cmp2(pair<LL,int> a,pair<LL,int> b)
{
    return a>b;
}
void work()
{
    pp.clear();
    scanf("%d",&n);
    int m,q; 
    scanf("%d",&q);
    demension=2;
    
   for(int i=1;i<=n;i++)
    {
        for(int j=0;j<demension;j++)
            scanf("%lld",&T[i].pos[j]);
        T[i].id=i;
        scanf("%lld",&T[i].c);
        pp.pb(mk(T[i].c,i));
    }
    
    sort(pp.begin(),pp.end(),cmp2);
    
    build(1,n);
    
    for(int i=1;i<=q;i++)
    {
        for(int j=0;j<demension;j++)
            scanf("%lld",&W[i].pos[j]);
        W[i].id=i;
        scanf("%lld",&W[i].c);
    }
    
    sort(W+1,W+q+1,cmp1);
    
    memset(use,0,sizeof(use));
    int la=0;
    for(int i=1;i<=q;i++)
    {
        while(pp[la].first>W[i].c&&la!=pp.size())
        {
            use[pp[la].second]=1;
            la++;
        }
        op=W[i];
        /*for(int j=0;j<demension;j++)
        {
            printf("%lld",W[i].pos[j]);
            printf(" ");
        }
        printf("%lld **\n",W[i].c);*/
        ans=(((LL)INT_INF)*INT_INF);
        query(1,n);
        an[W[i].id]=point;
        /*cout<<ans<<endl;
        for(int j=0;j<demension;j++)
        {
            printf("%lld",point.pos[j]);
            printf(" ");
        }
        printf("%lld *\n",point.c);*/
    }
    for(int i=1;i<=q;i++)
    {
        for(int j=0;j<demension;j++)
        {
            printf("%lld",an[i].pos[j]);
            printf(" ");
        }
        printf("%lld\n",an[i].c);
    }
    return;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--) work();
    return 0;
}