fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Rect{
  5. int x1,y1,x2,y2,id;
  6. bool contains(int x,int y)const{
  7. return x>=x1&&x<=x2&&y>=y1&&y<=y2;
  8. }
  9. };
  10. static vector<Rect> R; // global store for quick access
  11. const int CAP=1, MAXD=16; // capacity per leaf and safety depth
  12.  
  13. struct Node{
  14. int x1,y1,x2,y2;
  15. vector<int> ids; // rectangle indices living here
  16. Node* ch[4]{nullptr,nullptr,nullptr,nullptr}; // NW,NE,SW,SE
  17. Node(int a,int b,int c,int d):x1(a),y1(b),x2(c),y2(d){}
  18. bool leaf()const{return ch[0]==nullptr;}
  19. };
  20.  
  21. void split(Node* n){
  22. int mx=(n->x1+n->x2)/2, my=(n->y1+n->y2)/2;
  23. n->ch[0]=new Node(n->x1,n->y1,mx,my); // NW
  24. n->ch[1]=new Node(mx+1,n->y1,n->x2,my); // NE
  25. n->ch[2]=new Node(n->x1,my+1,mx,n->y2); // SW
  26. n->ch[3]=new Node(mx+1,my+1,n->x2,n->y2); // SE
  27. }
  28.  
  29. bool intersects(const Node* n,const Rect& r){
  30. return !(r.x2<n->x1||r.x1>n->x2||r.y2<n->y1||r.y1>n->y2);
  31. }
  32.  
  33. void insert(Node* n,int idx,int depth){
  34. if(depth==MAXD|| (n->x1==n->x2 && n->y1==n->y2) ){
  35. n->ids.push_back(idx); // cannot subdivide
  36. return;
  37. }
  38. if(n->leaf() && (int)n->ids.size()<CAP){
  39. n->ids.push_back(idx);
  40. return;
  41. }
  42. if(n->leaf()) { split(n); // first time split
  43. vector<int> old = move(n->ids); // re-distribute old
  44. for(int id:old) insert(n,id,depth+1);
  45. }
  46. for(int k=0;k<4;++k) if(intersects(n,R[idx])) insert(n->ch[k],idx,depth+1);
  47. }
  48.  
  49. Node* buildQuadTree(const vector<Rect>& rects,int W,int H){
  50. R=rects;
  51. Node* root=new Node(0,0,W,H);
  52. for(int i=0;i<(int)R.size();++i) insert(root,i,0);
  53. return root;
  54. }
  55.  
  56. int query(Node* n,int x,int y){
  57. int ans=-1;
  58. for(int id:n->ids) if(R[id].contains(x,y)) ans=max(ans,id);
  59. if(n->leaf()) return ans;
  60. int mx=(n->x1+n->x2)/2, my=(n->y1+n->y2)/2, idx;
  61. if(y<=my) idx = (x<=mx?0:1); else idx = (x<=mx?2:3);
  62. return max(ans, query(n->ch[idx],x,y));
  63. }
  64. int main(){
  65. vector<Rect> rects={
  66. {10,10,60,60,0},
  67. {40,40,90,90,1},
  68. {70,10,110,50,2}
  69. };
  70. Node* root = buildQuadTree(rects,127,127);
  71. cout<<query(root,45,45)<<'\n'; // prints 1 (top rectangle)
  72. }
Success #stdin #stdout 0s 5320KB
stdin
Standard input is empty
stdout
1