hdu 4347 The Closest M Points (kd-tree+优先队列，求M近邻)

2017年10月9日 0 作者 CrazyKK

题目链接

题意：

给出若干个点，在给出一个定点，求距离该定点最近的m个点。

思路：

我们已经知道kd-tree可以得到最近邻，实际上M近邻，只需要维护一个size为M的优先队列就可以了。

需要注意，优先队列的元素一定要先定义小于关系orz

以及这次采用了轮盘转的策略划分维度，也就是按照深度，所有维度轮流作为split-method（实际用起来效果还是挺棒的orz

C++
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
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2017年10月08日 星期日 23时18分42秒
File Name :4347.cpp
************************************************ */
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
 
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=5E4+7;
const int M = 10;
int n,m,k,t;
int idx;
struct Point
{
    LL coor[M];
    int id;
    void print()
    {
    for ( int i = 1 ; i <= k ; i++)
        printf("%lld%c",coor[i],i==k?'\n':' ');
    }
    bool operator < (const Point &u)const
    {
    return coor[idx]<u.coor[idx];
    }
}po[N];
typedef pair< LL,Point >PI;
priority_queue< PI >pq; //用优先队列一定要定义小于关系啊orz...我怎么这么傻
struct KdTree
{
    Point p[N<<2];
    bool leaf[N<<2];
    void build ( int l,int r, int rt = 1,int dep=0)
    {
    if (l>r) return;
    leaf[rt] = false;
    leaf[rt<<1] = leaf[rt<<1|1] = true;
    idx = dep % k;
    int mid = (l+r)>>1;
    nth_element(po+l,po+mid,po+r+1);
    p[rt] = po[mid];
    build(l,mid-1, rt<<1,dep+1);
    build(mid+1,r,rt<<1|1,dep+1);
    }
    void query(Point tar,int rt=1,int dep=0)
    {
    if (leaf[rt]) return;
    PI cur(0,p[rt]);
    for ( int i = 1 ; i <= k ; i++) cur.fst += (p[rt].coor[i]-tar.coor[i])*(p[rt].coor[i]-tar.coor[i]);
    int idx = dep%k;
    int x=rt<<1,y=rt<<1|1,flag=0;
    LL d = tar.coor[idx]-p[rt].coor[idx];
    if (d>0) swap(x,y);
    if (!leaf[x]) query(tar,x,dep+1);
    if (pq.size()<m) pq.push(cur),flag=1;
    else
    {
        if (cur.fst < pq.top().fst) pq.pop(),pq.push(cur);
        if (d*d<pq.top().fst) flag = 1;
    }
    //cout<<pq.top().second.coor[0]<<" "<<pq.top().second.coor[1]<<endl;
    if (!leaf[y]&&flag) query(tar,y,dep+1);
    }
}kd;
int main()
{
    #ifndef  ONLINE_JUDGE
    freopen("./in.txt","r",stdin);
  #endif
    while (~scanf("%d %d",&n,&k))
    {
        for ( int i = 1 ;  i <= n ; i++)
        {
        for ( int j = 1 ; j <= k ; j++) scanf("%lld",&po[i].coor[j]);
        }
        scanf("%d",&t);
        kd.build(1,n);
        while (t--)
        {
        Point ask;
        for ( int i = 1 ; i <= k ; i++) scanf("%lld",&ask.coor[i]);
        scanf("%d",&m);
        kd.query(ask);
        printf("the closest %d points are:\n",m);
        Point ret[20];
        //cout<<"pq_siz:"<<pq.size()<<" pq.top()"<<pq.top().sec.coor[1]<<endl;
        for ( int i = 1 ; !pq.empty() ; i++) ret[i] = pq.top().second,pq.pop();
        for ( int i = m ; i >= 1 ; i--)  ret[i].print();
        }
    }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}
 
 
 
 

 

 

分类目录hdoj
标签kd-tree 优先队列

关于作者

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！

提醒
wpDiscuz