| 44 | kd_tree(vector<pt> pts) { |
| 45 | root = construct(pts, 0, (int)size(pts) - 1, 0); } |
| 46 | node* construct(vector<pt> &pts, int from, int to, int c) { |
| 47 | if (from > to) return NULL; |
| 48 | int mid = from + (to - from) / 2; |
| 49 | nth_element(pts.begin() + from, pts.begin() + mid, |
| 50 | pts.begin() + to + 1, cmp(c)); |
| 51 | return new node(pts[mid], |
| 52 | construct(pts, from, mid - 1, INC(c)), |
| 53 | construct(pts, mid + 1, to, INC(c))); } |
| 54 | bool contains(const pt &p) { return _con(p, root, 0); } |
| 55 | bool _con(const pt &p, node *n, int c) { |
| 56 | if (!n) return false; |