posts - 4,  comments - 0,  trackbacks - 0
          寫個kd-tree模板...無它
          UPD: 以前寫的代碼太難看啦,趁去南京賽區之前整理模板重寫了一下...

            1 //hdu4347 KD Tree
            2 //詢問k維空間中距某點最近的m個點
            3 
            4 #include <cstdio>
            5 #include <queue>
            6 #include <algorithm>
            7 
            8 using namespace std;
            9 
           10 const int N = 200010;
           11 const int DIM = 5;
           12 
           13 inline double sqr(double x) { return x*x; }
           14 
           15 int k, n;        //k為維數, n為點數
           16 
           17 struct Point {
           18     int x[DIM];
           19     double cald(Point o) {
           20         double ret = 0;
           21         for (int i = 0; i < k; i++) {
           22             ret += sqr(x[i] - o.x[i]);
           23         }
           24         return ret;
           25     }
           26     void print() {
           27         for (int i = 0; i < k; i++) {
           28             printf("%d", x[i]);
           29             i == k - 1 ? puts("") : printf(" ");
           30         }
           31     }
           32 }point[N];
           33 
           34 struct Heap_t {
           35     Point p; double dis;
           36     Heap_t() {}
           37     Heap_t(Point _p, double _dis) : p(_p), dis(_dis) {}
           38     bool operator < (const Heap_t &o) const {
           39         return dis < o.dis;
           40     }
           41 };
           42 
           43 priority_queue<Heap_t> q;        //維護前m大數
           44 
           45 //笨方法,用于對動態第dim維排序,通過修改全局變量dim來達到目的
           46 int dim;
           47 bool cmp(Point a, Point b) {
           48     return a.x[dim] < b.x[dim];
           49 }
           50 
           51 struct KDTree {
           52     struct Node {
           53         Point p;
           54         int size;
           55     }t[N];
           56     inline int LC(int x) { return x << 1; }
           57     inline int RC(int x) { return x << 1 | 1; }
           58     //建樹,采取wiki上的建樹方法
           59     void build(Point p[], int l, int r, int rt, int dep) {
           60         if (l > r) return;
           61         t[rt].size = r - l;
           62         t[LC(rt)].size = t[RC(rt)].size = -1;
           63         dim = dep % k;
           64         int m = (l + r) >> 1;
           65         nth_element(p + l, p + m, p + r + 1, cmp);
           66         t[rt].p = p[m];
           67         build(p, l, m - 1, LC(rt), dep + 1);
           68         build(p, m + 1, r, RC(rt), dep + 1);
           69     }
           70     void insert(Heap_t h) {
           71         if (h.dis < q.top().dis) {
           72             q.pop(); q.push(h);
           73         }
           74     }
           75     //詢問前m近的點。
           76     //與最近鄰相似,先一路搜到葉子,然后如果當前得到的點數<m時,要搜索所有的子樹。
           77     //得到m個點之后就維護一個大小為m的堆,當前節點距離<堆頂元素距離時,將當前節點加入,堆頂元素彈出。
           78     //其余與最近鄰詢問相似。
           79     void query(Point p, int rt, int dep, int m) {
           80         if (t[rt].size == -1return;
           81         Heap_t h(t[rt].p, t[rt].p.cald(p));
           82         int dim = dep % k;
           83         if (p.x[dim] < t[rt].p.x[dim]) {
           84             query(p, LC(rt), dep + 1, m);
           85             if (q.size() < m) {
           86                 q.push(h);
           87                 query(p, RC(rt), dep + 1, m);
           88             } else {
           89                 insert(h);
           90                 //如果要查詢的點與超平面的距離 < 堆頂元素的距離,則要到另一邊超平面去查詢
           91                 if (sqr(p.x[dim] - t[rt].p.x[dim]) < q.top().dis) {
           92                     query(p, RC(rt), dep + 1, m);
           93                 }
           94             }
           95         } else {
           96             query(p, RC(rt), dep + 1, m);
           97             if (q.size() < m) {
           98                 q.push(h);
           99                 query(p, LC(rt), dep + 1, m);
          100             } else {
          101                 insert(h);
          102                 if (sqr(p.x[dim] - t[rt].p.x[dim]) < q.top().dis) {
          103                     query(p, LC(rt), dep + 1, m);
          104                 }
          105             }
          106         }
          107     }
          108 }kdt;
          109 
          110 int main() {
          111     while (~scanf("%d%d"&n, &k)) {
          112         for (int i = 0; i < n; i++) {
          113             for (int j = 0; j < k; j++) {
          114                 scanf("%d"&point[i].x[j]);
          115             }
          116         }
          117         kdt.build(point, 0, n - 110);
          118         int t; scanf("%d"&t);
          119         for (int i = 0; i < t; i++) {
          120             Point ask;
          121             for (int j = 0; j < k; j++) {
          122                 scanf("%d"&ask.x[j]);
          123             }
          124             int m; scanf("%d"&m);
          125             kdt.query(ask, 10, m);
          126             Point p[10];
          127             for (int j = 0!q.empty(); j++) {
          128                 p[j] = q.top().p; q.pop();
          129             }
          130             printf("the closest %d points are:\n", m);
          131             for (int j = m - 1; j >= 0; j--) {
          132                 p[j].print();
          133             }
          134         }
          135     }
          136     return 0;
          137 }

          允許轉載,轉載請注明出處:
          posted on 2012-08-13 22:35 NKU->lkjslkjdlk 閱讀(679) 評論(0)  編輯  收藏

          只有注冊用戶登錄后才能發表評論。


          網站導航:
           
          <2012年8月>
          2930311234
          567891011
          12131415161718
          19202122232425
          2627282930311
          2345678

          常用鏈接

          留言簿

          隨筆檔案

          搜索

          •  

          最新評論

          閱讀排行榜

          評論排行榜

          主站蜘蛛池模板: 房山区| 开阳县| 军事| 陕西省| 溧阳市| 宁津县| 永平县| 大名县| 邳州市| 松滋市| 蓬溪县| 阳江市| 阳谷县| 平和县| 邵武市| 长春市| 广河县| 岐山县| 吴川市| 故城县| 兰州市| 威海市| 客服| 京山县| 抚顺县| 安宁市| 连城县| 甘肃省| 辽阳县| 大田县| 平塘县| 大港区| 宜昌市| 老河口市| 沁水县| 灯塔市| 本溪市| 阜新市| 河津市| 交城县| 西宁市|