Pagini recente » Cod sursa (job #81739) | Cod sursa (job #3177824) | Cod sursa (job #62978) | Cod sursa (job #3224164) | Cod sursa (job #3162616)
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("zoo.in");
ofstream cout("zoo.out");
struct coord_dreptunghi
{
int x1,y1,x2,y2;
} d[100002];
pair<int,int>coord[16002];
vector<int>aint[5*100001];
int p[5*100000+5],nr,n,m,sol;
int cb(int a)
{
int st=0;
int dr=nr;
while(st<=dr)
{
int mid=(st+dr)/2;
if(p[mid]==a)
return mid;
else if(p[mid]>a)
dr=mid-1;
else
st=mid+1;
}
}
int cb_primul(int a,int nod)
{
int st=0;
int dr=aint[nod].size()-1;
while(st<=dr)
{
int mid=(st+dr)/2;
if(aint[nod][mid]>=a)
dr=mid-1;
else
st=mid+1;
}
return st;
}
int cb_ultim(int a,int nod)
{
int st=0;
int dr=aint[nod].size()-1;
while(st<=dr)
{
int mid=(st+dr)/2;
if(aint[nod][mid]<=a)
st=mid+1;
else
dr=mid-1;
}
return dr;
}
void build(int nod,int st,int dr)
{
for(int i=st; i<=dr; i++)
aint[nod].push_back(coord[i].second);
sort(aint[nod].begin(), aint[nod].end());
if(st<dr)
{
int mid=(st+dr)/2;
build(2*nod,st,mid);
build(2*nod+1,mid+1,dr);
}
}
void query(int nod,int st,int dr,int nr_drept)
{
if(d[nr_drept].x1<=coord[st].first&&coord[dr].first<=d[nr_drept].x2)
sol+=cb_ultim(d[nr_drept].y2,nod)-cb_primul(d[nr_drept].y1,nod)+1;
else
{
if(st==dr)
return;
int mid=(st+dr)/2;
if(d[nr_drept].x1<=coord[mid].first)
query(2*nod,st,mid,nr_drept);
if(d[nr_drept].x2>coord[mid+1].first)
query(2*nod+1,mid+1,dr,nr_drept);
}
}
int main()
{
cin>>n;
///normalizare
for(int i=1; i<=n; i++)
{
cin>>coord[i].first>>coord[i].second;
p[nr++]=coord[i].first;
p[nr++]=coord[i].second;
}
cin>>m;
for(int i=1; i<=m; i++)
{
cin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2;
p[nr++]=d[i].x1;
p[nr++]=d[i].y1;
p[nr++]=d[i].x2;
p[nr++]=d[i].y2;
}
sort(p,p+nr);
int aux=0;
for(int i=1; i<nr; i++)
if(p[aux]!=p[i])
{
p[++aux]=p[i];
}
nr=aux ;
for(int i=1; i<=n; i++)
{
coord[i].first=cb(coord[i].first);
coord[i].second=cb(coord[i].second);
}
for(int 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(coord+1,coord+n+1);
build(1,1,n);///construim arborele de intervale in care adaugam fiecare punct in intervalele din care face parte
for(int i=1; i<=m; i++)
{
sol=0;
query(1,1,n,i);
cout<<sol<<'\n';
}
return 0;
}