Pagini recente » Cod sursa (job #2155058) | Cod sursa (job #1940456) | Cod sursa (job #1170991) | Cod sursa (job #1224865) | Cod sursa (job #615724)
Cod sursa(job #615724)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const char InFile[]="zoo.in";
const char OutFile[]="zoo.out";
const int MaxN=16111;
const int AINT_SIZE=MaxN<<2;
ifstream fin(InFile);
ofstream fout(OutFile);
struct point
{
point(int x=0, int y=0):x(x),y(y){}
int x,y;
};
struct cmp_point_x
{
inline bool operator() (const point &a, const point &b)
{
return a.x<b.x;
}
};
struct aint_node
{
vector<int> y;
};
int N,M,sol,xmin,ymin,xmax,ymax,pst,pdr,v[MaxN];
point p[MaxN];
aint_node aint[AINT_SIZE];
inline void cauta(int nod)
{
int p=0,u=aint[nod].y.size()-1;
while(p<=u)
{
int m=p+((u-p)>>1);
if(aint[nod].y[m]>=ymin)
{
u=m-1;
}
else
{
p=m+1;
}
}
int st=p;
p=0,u=aint[nod].y.size()-1;
while(p<=u)
{
int m=p+((u-p)>>1);
if(aint[nod].y[m]<=ymax)
{
p=m+1;
}
else
{
u=m-1;
}
}
int dr=u;
sol+=dr-st+1;
}
void init(int nod, int st, int dr)
{
if(st==dr)
{
aint[nod].y.push_back(p[st].y);
return;
}
int l=nod<<1;
int mid=st+((dr-st)>>1);
init(l,st,mid);
init(l+1,mid+1,dr);
unsigned int ind1=0;
unsigned int ind2=0;
while(ind1<aint[l].y.size() && ind2<aint[l+1].y.size())
{
if(aint[l].y[ind1]<aint[l+1].y[ind2])
{
aint[nod].y.push_back(aint[l].y[ind1]);
++ind1;
}
else
{
aint[nod].y.push_back(aint[l+1].y[ind2]);
++ind2;
}
}
while(ind1<aint[l].y.size())
{
aint[nod].y.push_back(aint[l].y[ind1]);
++ind1;
}
while(ind2<aint[l+1].y.size())
{
aint[nod].y.push_back(aint[l+1].y[ind2]);
++ind2;
}
}
void query(int nod, int st, int dr)
{
if(pst<=st && dr<=pdr)
{
cauta(nod);
return;
}
int mid=st+((dr-st)>>1);
nod<<=1;
if(pst<=mid)
{
query(nod,st,mid);
}
if(mid<pdr)
{
query(nod+1,mid+1,dr);
}
}
int main()
{
fin>>N;
for(register int i=1;i<=N;++i)
{
fin>>p[i].x>>p[i].y;
}
sort(p+1,p+1+N,cmp_point_x());
for(register int i=1;i<=N;++i)
{
v[i]=p[i].x;
}
init(1,1,N);
fin>>M;
for(register int i=1;i<=M;++i)
{
sol=0;
fin>>xmin>>ymin>>xmax>>ymax;
int p=1,u=N;
while(p<=u)
{
int m=p+((u-p)>>1);
if(v[m]>=xmin)
{
u=m-1;
}
else
{
p=m+1;
}
}
pst=p;
p=1;u=N;
while(p<=u)
{
int m=p+((u-p)>>1);
if(v[m]<=xmax)
{
p=m+1;
}
else
{
u=m-1;
}
}
pdr=u;
if(1<=pst && pst<=pdr && pdr<=N)
{
query(1,1,N);
}
fout<<sol<<"\n";
}
fin.close();
fout.close();
return 0;
}