Pagini recente » Cod sursa (job #3217773) | Cod sursa (job #94610) | Cod sursa (job #214987) | Cod sursa (job #59875) | Cod sursa (job #3163412)
#include <bits/stdc++.h>
#define DIMN 16001
#define DIMM 100001
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct coord{
int x;
int y;
}p[DIMN];
struct dreptunghi{
int x1;
int x2;
int y1;
int y2;
}d[DIMM];
int i, j, len, n, m, poz, ans;
int s[DIMM*5];
vector <int> arb[4*(DIMM+DIMN)];
bool comp(coord x, coord y){
return (x.x<y.y);
}
int cb(int x){
int st=0, dr=len;
while(st<=dr){
int mij=(st+dr)/2;
if(x==s[mij])
return mij;
else
if(x<s[mij])
dr=mij-1;
else st=mij+1;
}
}
int cbst(int x, int nod){
int st=0, dr=arb[nod].size()-1;
while(st<=dr){
int mij=(st+dr)/2;
if(x<=arb[nod][mij])
dr=mij-1;
else st=mij+1;
return st;
}
}
int cbdr(int x, int nod){
int st=0, dr=arb[nod].size()-1;
while(st<=dr){
int mij=(st+dr)/2;
if(x>=arb[nod][mij])
st=mij+1;
else dr=mij-1;
return dr;
}
}
void build(int nod, int st, int dr){
for(i=st; i<=dr; i++)
arb[nod].push_back(p[i].y);
sort(arb[nod].begin(), arb[nod].end());
if(st<dr){
int mij=(st+dr)/2;
build(nod*2, st, mij);
build(nod*2+1, mij+1, dr);
}
}
void query(int nod, int st, int dr, int q){
if(st>dr)
return;
if(d[q].x1<=p[st].x && p[dr].x<=d[q].x2){
ans+=(cbdr(d[q].y2, nod)-cbst(d[q].y1, nod)+1);
}else{
if(st==dr)
return;
int mij=(st+dr)/2;
if(d[q].x1<=p[mij].x)
query(nod*2, st, mij, q);
if(d[q].x2>=p[mij+1].x)
query(nod*2+1, mij+1, dr, q);
}
}
int main(){
fin >> n;
for(i=1; i<=n; i++){
fin>>p[i].x>>p[i].y;
s[len++]=p[i].x;
s[len++]=p[i].y;
}
fin>>m;
for(i=1; i<=m; i++){
fin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2;
s[len++]=d[i].x1;
s[len++]=d[i].y1;
s[len++]=d[i].x2;
s[len++]=d[i].y2;
}
sort(s, s+len);
for(i=1; i<len; i++)
if(s[i]!=s[poz])
s[++poz]=s[i];
len=poz+1;
for(i=1; i<=n; i++){
p[i].x=cb(p[i].x);
p[i].y=cb(p[i].y);
}
for(i=1; i<=m; i++){
d[i].x1=cb(d[i].x1);
d[i].y1=cb(d[i].y1);
d[i].x2=cb(d[i].x2);
d[i].y2=cb(d[i].y2);
}
sort(p+1, p+n+1, comp);
build(1, 1, n);
for(i=1; i<=m; i++){
ans=0;
query(1, 1, n, i);
fout<<ans<<"\n";
}
}