#include <bits/stdc++.h> using namespace std; const int maxn = 1e6; struct Node{ int pos; int l, r; Node(){}; Node(int pos, int l, int r):pos(pos), l(l), r(r){}; }; struct Point{ int id, x, y; Point(){}; Point(int _id, int _x, int _y):id(_id), x(_x), y(_y){}; bool operator < (const Point &p)const{ return id<p.id; } }; bool cmpx(Point a, Point b){return a.x<b.x;} bool cmpy(Point a, Point b){return a.y<b.y;} int n; Point p[maxn]; Node node[maxn]; int rt; int cnt = 0; int make_kdtree(int l, int r, int depth){ if(!(l<r)) return -1; int mid = (l+r)/2; if(depth%2 == 0){ sort(p+l, p+r, cmpx); } else{ sort(p+l, p+r, cmpy); } int t = rt++; node[t].pos = mid; node[t].l = make_kdtree(l, mid, depth+1); node[t].r = make_kdtree(mid+1, r, depth+1); return t; } void find_node(int rt, int sx, int tx, int sy, int ty, int depth, vector<Point> &ans){ int x = p[node[rt].pos].x; int y = p[node[rt].pos].y; if(x>=sx&&x<=tx&&y<=ty&&y>=sy){ ans.push_back(p[node[rt].pos]); } if(depth%2 == 0){ if(node[rt].l!=-1){ if(sx<=x){ find_node(node[rt].l, sx, tx, sy, ty, depth+1, ans); } } if(node[rt].r!=-1){ if(x<=tx){ find_node(node[rt].r, sx, tx, sy, ty, depth+1, ans); } } } else{ if(node[rt].l!=-1){ if(sy<=y){ find_node(node[rt].l, sx, tx,sy,ty, depth+1, ans); } } if(node[rt].r!=-1){ if(y<=ty){ find_node(node[rt].r, sx, tx, sy, ty, depth+1, ans); } } } } int main() { while(~scanf("%d", &n)){ for(int i=0; i<n; i++){ int x, y; scanf("%d%d", &x, &y); p[i].x = x, p[i].y = y, p[i].id = i; node[i].l = node[i].r = node[i].pos = -1; } rt = 0; int root = make_kdtree(0, n, 0); int q; scanf("%d", &q); int sx, sy, tx, ty; vector<Point> ans; for(int i=0; i<q; i++){ scanf("%d%d%d%d", &sx, &tx, &sy, &ty); ans.clear(); find_node(root, sx, tx, sy, ty, 0, ans); sort(ans.begin(), ans.end()); for(vector<Point>::iterator it = ans.begin(); it!=ans.end(); it++){ printf("%d\n", it->id); } printf("\n"); } } return 0; }
|