Pagini recente » Cod sursa (job #974855) | Cod sursa (job #1803253) | Cod sursa (job #89705) | Cod sursa (job #2262748) | Cod sursa (job #1227554)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct points
{
int x,y;
};
struct drept
{
int x,y,w,z;
int indice;
};
struct comp
{
bool operator () (const int& A,const int& B) const
{
return A>B;
}
};
const int NMAX=16005;
const int MMAX=100005;
int n,m,sol[MMAX],c[NMAX];
vector<points>v[NMAX];
vector<points>::iterator it;
points a[NMAX];
drept b[MMAX];
multiset<int>s;
multiset<int,comp>p;
multiset<int>::iterator pit;
inline bool cmp(const points A,const points B)
{
return A.x<B.x;
}
int main()
{
int i,poz,aux,nr;
points d;
fin>>n;
for (i=1;i<=n;i++) fin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
for (i=1;i<=n;i++) c[i]=a[i].x;
fin>>m;
for (i=1;i<=m;i++)
{
fin>>b[i].x>>b[i].y>>b[i].w>>b[i].z;
b[i].indice=i;
d.x=i;
d.y=-1;
poz=lower_bound(c+1,c+n+1,b[i].x)-c;
poz--;
v[poz].push_back(d);
d.y=1;
poz=upper_bound(c+1,c+n+1,b[i].w)-c;
if (c[poz]>b[i].w || poz>n) poz--;
v[poz].push_back(d);
}
for (i=1;i<=n;i++)
{
s.insert(a[i].y);
for (it=v[i].begin();it!=v[i].end();it++)
{
d=*it;
pit=lower_bound(s.begin(),s.end(),b[i].y);
nr=0;
while (pit!=s.end() && (*pit)>=b[d.x].y && (*pit)<=b[d.x].w)
{
nr++;
pit++;
}
if (d.y==-1) sol[d.x]-=nr;
else sol[d.x]+=nr;
}
}
for (i=1;i<=m;i++) fout<<sol[i]<<"\n";
return 0;
}