#include <bits/stdc++.h>
using namespace std;
struct Rect{
int x1,y1,x2,y2,id;
bool contains(int x,int y)const{
return x>=x1&&x<=x2&&y>=y1&&y<=y2;
}
};
static vector<Rect> R; // global store for quick access
const int CAP=1, MAXD=16; // capacity per leaf and safety depth
struct Node{
int x1,y1,x2,y2;
vector<int> ids; // rectangle indices living here
Node* ch[4]{nullptr,nullptr,nullptr,nullptr}; // NW,NE,SW,SE
Node(int a,int b,int c,int d):x1(a),y1(b),x2(c),y2(d){}
bool leaf()const{return ch[0]==nullptr;}
};
void split(Node* n){
int mx=(n->x1+n->x2)/2, my=(n->y1+n->y2)/2;
n->ch[0]=new Node(n->x1,n->y1,mx,my); // NW
n->ch[1]=new Node(mx+1,n->y1,n->x2,my); // NE
n->ch[2]=new Node(n->x1,my+1,mx,n->y2); // SW
n->ch[3]=new Node(mx+1,my+1,n->x2,n->y2); // SE
}
bool intersects(const Node* n,const Rect& r){
return !(r.x2<n->x1||r.x1>n->x2||r.y2<n->y1||r.y1>n->y2);
}
void insert(Node* n,int idx,int depth){
if(depth==MAXD|| (n->x1==n->x2 && n->y1==n->y2) ){
n->ids.push_back(idx); // cannot subdivide
return;
}
if(n->leaf() && (int)n->ids.size()<CAP){
n->ids.push_back(idx);
return;
}
if(n->leaf()) { split(n); // first time split
vector<int> old = move(n->ids); // re-distribute old
for(int id:old) insert(n,id,depth+1);
}
for(int k=0;k<4;++k) if(intersects(n,R[idx])) insert(n->ch[k],idx,depth+1);
}
Node* buildQuadTree(const vector<Rect>& rects,int W,int H){
R=rects;
Node* root=new Node(0,0,W,H);
for(int i=0;i<(int)R.size();++i) insert(root,i,0);
return root;
}
int query(Node* n,int x,int y){
int ans=-1;
for(int id:n->ids) if(R[id].contains(x,y)) ans=max(ans,id);
if(n->leaf()) return ans;
int mx=(n->x1+n->x2)/2, my=(n->y1+n->y2)/2, idx;
if(y<=my) idx = (x<=mx?0:1); else idx = (x<=mx?2:3);
return max(ans, query(n->ch[idx],x,y));
}
int main(){
vector<Rect> rects={
{10,10,60,60,0},
{40,40,90,90,1},
{70,10,110,50,2}
};
Node* root = buildQuadTree(rects,127,127);
cout<<query(root,45,45)<<'\n'; // prints 1 (top rectangle)
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgUmVjdHsKICAgIGludCB4MSx5MSx4Mix5MixpZDsKICAgIGJvb2wgY29udGFpbnMoaW50IHgsaW50IHkpY29uc3R7CiAgICAgICAgcmV0dXJuIHg+PXgxJiZ4PD14MiYmeT49eTEmJnk8PXkyOwogICAgfQp9OwpzdGF0aWMgdmVjdG9yPFJlY3Q+IFI7ICAgICAgICAgIC8vIGdsb2JhbCBzdG9yZSBmb3IgcXVpY2sgYWNjZXNzCmNvbnN0IGludCBDQVA9MSwgTUFYRD0xNjsgICAgICAgLy8gY2FwYWNpdHkgcGVyIGxlYWYgYW5kIHNhZmV0eSBkZXB0aAoKc3RydWN0IE5vZGV7CiAgICBpbnQgeDEseTEseDIseTI7CiAgICB2ZWN0b3I8aW50PiBpZHM7ICAgICAgICAgICAgLy8gcmVjdGFuZ2xlIGluZGljZXMgbGl2aW5nIGhlcmUKICAgIE5vZGUqIGNoWzRde251bGxwdHIsbnVsbHB0cixudWxscHRyLG51bGxwdHJ9OyAgICAgIC8vIE5XLE5FLFNXLFNFCiAgICBOb2RlKGludCBhLGludCBiLGludCBjLGludCBkKTp4MShhKSx5MShiKSx4MihjKSx5MihkKXt9CiAgICBib29sIGxlYWYoKWNvbnN0e3JldHVybiBjaFswXT09bnVsbHB0cjt9Cn07Cgp2b2lkIHNwbGl0KE5vZGUqIG4pewogICAgaW50IG14PShuLT54MStuLT54MikvMiwgbXk9KG4tPnkxK24tPnkyKS8yOwogICAgbi0+Y2hbMF09bmV3IE5vZGUobi0+eDEsbi0+eTEsbXgsbXkpOyAgICAgIC8vIE5XCiAgICBuLT5jaFsxXT1uZXcgTm9kZShteCsxLG4tPnkxLG4tPngyLG15KTsgICAgLy8gTkUKICAgIG4tPmNoWzJdPW5ldyBOb2RlKG4tPngxLG15KzEsbXgsbi0+eTIpOyAgICAvLyBTVwogICAgbi0+Y2hbM109bmV3IE5vZGUobXgrMSxteSsxLG4tPngyLG4tPnkyKTsgIC8vIFNFCn0KCmJvb2wgaW50ZXJzZWN0cyhjb25zdCBOb2RlKiBuLGNvbnN0IFJlY3QmIHIpewogICAgcmV0dXJuICEoci54MjxuLT54MXx8ci54MT5uLT54Mnx8ci55MjxuLT55MXx8ci55MT5uLT55Mik7Cn0KCnZvaWQgaW5zZXJ0KE5vZGUqIG4saW50IGlkeCxpbnQgZGVwdGgpewogICAgaWYoZGVwdGg9PU1BWER8fCAobi0+eDE9PW4tPngyICYmIG4tPnkxPT1uLT55MikgKXsKICAgICAgICBuLT5pZHMucHVzaF9iYWNrKGlkeCk7ICAgICAgICAgICAgICAgICAgICAgICAgLy8gY2Fubm90IHN1YmRpdmlkZQogICAgICAgIHJldHVybjsKICAgIH0KICAgIGlmKG4tPmxlYWYoKSAmJiAoaW50KW4tPmlkcy5zaXplKCk8Q0FQKXsKICAgICAgICBuLT5pZHMucHVzaF9iYWNrKGlkeCk7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaWYobi0+bGVhZigpKSB7IHNwbGl0KG4pOyAgICAgICAgICAgICAgICAgICAgICAgICAvLyBmaXJzdCB0aW1lIHNwbGl0CiAgICAgICAgdmVjdG9yPGludD4gb2xkID0gbW92ZShuLT5pZHMpOyAgICAgICAgICAgICAgIC8vIHJlLWRpc3RyaWJ1dGUgb2xkCiAgICAgICAgZm9yKGludCBpZDpvbGQpIGluc2VydChuLGlkLGRlcHRoKzEpOwogICAgfQogICAgZm9yKGludCBrPTA7azw0OysraykgaWYoaW50ZXJzZWN0cyhuLFJbaWR4XSkpIGluc2VydChuLT5jaFtrXSxpZHgsZGVwdGgrMSk7Cn0KCk5vZGUqIGJ1aWxkUXVhZFRyZWUoY29uc3QgdmVjdG9yPFJlY3Q+JiByZWN0cyxpbnQgVyxpbnQgSCl7CiAgICBSPXJlY3RzOwogICAgTm9kZSogcm9vdD1uZXcgTm9kZSgwLDAsVyxIKTsKICAgIGZvcihpbnQgaT0wO2k8KGludClSLnNpemUoKTsrK2kpIGluc2VydChyb290LGksMCk7CiAgICByZXR1cm4gcm9vdDsKfQoKaW50IHF1ZXJ5KE5vZGUqIG4saW50IHgsaW50IHkpewogICAgaW50IGFucz0tMTsKICAgIGZvcihpbnQgaWQ6bi0+aWRzKSBpZihSW2lkXS5jb250YWlucyh4LHkpKSBhbnM9bWF4KGFucyxpZCk7CiAgICBpZihuLT5sZWFmKCkpIHJldHVybiBhbnM7CiAgICBpbnQgbXg9KG4tPngxK24tPngyKS8yLCBteT0obi0+eTErbi0+eTIpLzIsIGlkeDsKICAgIGlmKHk8PW15KSBpZHggPSAoeDw9bXg/MDoxKTsgZWxzZSBpZHggPSAoeDw9bXg/MjozKTsKICAgIHJldHVybiBtYXgoYW5zLCBxdWVyeShuLT5jaFtpZHhdLHgseSkpOwp9CmludCBtYWluKCl7CiAgICB2ZWN0b3I8UmVjdD4gcmVjdHM9ewogICAgICAgIHsxMCwxMCw2MCw2MCwwfSwKICAgICAgICB7NDAsNDAsOTAsOTAsMX0sCiAgICAgICAgezcwLDEwLDExMCw1MCwyfQogICAgfTsKICAgIE5vZGUqIHJvb3QgPSBidWlsZFF1YWRUcmVlKHJlY3RzLDEyNywxMjcpOwogICAgY291dDw8cXVlcnkocm9vdCw0NSw0NSk8PCdcbic7ICAgLy8gcHJpbnRzIDEgKHRvcCByZWN0YW5nbGUpCn0=