Pagini recente » Cod sursa (job #871484) | Cod sursa (job #1639565) | Cod sursa (job #2799450) | Cod sursa (job #255175) | Cod sursa (job #1001629)
#include <fstream>
#include <algorithm>
using namespace std;
struct elem
{
int val;
int poz;
int fel;
}xg[216015],yg[216015];
struct cord
{
int x,y,poz,semn;
}v[16005],q[100005];
bool operator<(const cord &a,const cord &b)
{
if(a.x<b.x)
return 1;
if(a.x==b.x)
if(a.y<b.y)
return 1;
return 0;
}
bool operator<(const elem &a,const elem &b)
{
if(a.val<b.val)
return 1;
if(a.val>b.val)
return 0;
if(a.fel<b.fel)
return 1;
return 0;
}
bool cmp(const elem &a,const elem &b)
{
if(a.val<b.val)
return 1;
if(a.val>b.val)
return 0;
if(a.fel>b.fel)
return 1;
return 0;
}
int raspuns[100005];
int aib[100005],n;
#define inf 2000000000
#define lsb(x) (x&(-x))
void update(int x,int val)
{
int i;
for(i=x;i<=n;i+=lsb(i))
aib[i]+=val;
}
int sum(int x)
{
int i,sum=0;
for(i=x;i>0;i-=lsb(i))
sum+=aib[i];
return sum;
}
int main()
{
ifstream cin("zoo.in");
ofstream cout("zoo.out");
int m=0,i,j,x[16005],y[16005],ante,next,xi[100005],yi[100005],xs[100005],ys[100005];
cin>>n;
for(i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
xg[i].val=x[i];
xg[i].fel=0;
xg[i].poz=i;
yg[i].val=y[i];
yg[i].fel=0;
yg[i].poz=i;
}
cin>>m;
for(i=1;i<=m;i++)
{
cin>>xi[i]>>yi[i]>>xs[i]>>ys[i];
xg[n+(2*i)-1].val=xi[i];
xg[n+(2*i)-1].poz=i;
xg[n+(2*i)-1].fel=1;
yg[n+(2*i)-1].val=yi[i];
yg[n+(2*i)-1].poz=i;
yg[n+(2*i)-1].fel=1;
xg[n+(2*i)].val=xs[i];
xg[n+(2*i)].poz=i;
xg[n+(2*i)].fel=2;
yg[n+(2*i)].val=ys[i];
yg[n+(2*i)].poz=i;
yg[n+(2*i)].fel=2;
}
xg[0].val=-inf;
xg[0].fel=0;
xg[0].poz=0;
yg[0].val=-inf;
yg[0].fel=0;
yg[0].poz=0;
xg[n+(2*m)+1].val=inf;
xg[n+(2*m)+1].fel=0;
xg[n+(2*m)+1].poz=0;
yg[n+(2*m)+1].val=inf;
yg[n+(2*m)+1].fel=0;
yg[n+(2*m)+1].poz=0;
sort(xg+1,xg+(n+2*m+1));
sort(yg+1,yg+(n+2*m+1));
ante=-inf;
for(i=1;i<=(n+(2*m));i++)
if(xg[i].fel==0)
ante=xg[i].val;
else if (xg[i].fel==2)
xg[i].val=ante;
ante=-inf;
for(i=1;i<=(n+(2*m));i++)
{
if(yg[i].fel==0)
ante=yg[i].val;
else if(yg[i].fel==2)
yg[i].val=ante;
}
sort(xg+1,xg+(n+2*m+1),cmp);
sort(yg+1,yg+(n+2*m+1),cmp);
next=inf;
for(i=(n+(2*m));i>=1;i--)
{
if(xg[i].fel==0)
next=xg[i].val;
else if(xg[i].fel==1)
xg[i].val=next;
}
next=inf;
for(i=(n+(2*m));i>=1;i--)
{
if(yg[i].fel==0)
next=yg[i].val;
else if(yg[i].fel==1)
yg[i].val=next;
}
///////////////////////////
int pred;
int rasp=1;
pred=xg[1].val;
for(i=1;i<=(n+(2*m));i++)
{
if(xg[i].val!=pred)
{
pred=xg[i].val;
rasp++;
}
if(xg[i].fel==0)
x[xg[i].poz]=rasp;
else if(xg[i].fel==1)
xi[xg[i].poz]=rasp;
else
xs[xg[i].poz]=rasp;
}
///////////////////////
rasp=1;
pred=yg[1].val;
for(i=1;i<=(n+(2*m));i++)
{
if(yg[i].val!=pred)
{
pred=yg[i].val;
rasp++;
}
if(yg[i].fel==0)
y[yg[i].poz]=rasp;
else if(yg[i].fel==1)
yi[yg[i].poz]=rasp;
else
ys[yg[i].poz]=rasp;
}
/////////////////////////////////
for(i=1;i<=n;i++)
{
v[i].x=x[i];
v[i].y=y[i];
}
sort(v+1,v+n+1);
for(j=1;j<=m;j++)
{
q[4*j-3].x=xs[j];
q[4*j-3].y=ys[j];
q[4*j-3].poz=j;
q[4*j-3].semn=1;
q[4*j-2].x=xs[j];
q[4*j-2].y=yi[j]-1;
q[4*j-2].poz=j;
q[4*j-2].semn=-1;
q[4*j-1].x=xi[j]-1;
q[4*j-1].y=ys[j];
q[4*j-1].poz=j;
q[4*j-1].semn=-1;
q[4*j].x=xi[j]-1;
q[4*j].y=yi[j]-1;
q[4*j].poz=j;
q[4*j].semn=1;
}
sort(q+1,q+4*m+1); //ver dc n merg bine
int vechi=0;
vechi=v[1].x;
j=1;
while(j<=(4*m))
if(q[j].x==0)
j++;
else
break;
for(i=1;i<=n;)
{
while(i<=n)
if(v[i].x==vechi)
{
update(v[i].y,1);
i++;
}
else
{
break;
}
while(j<=(4*m))
if(q[j].x==vechi)
{
raspuns[q[j].poz]+=(sum(q[j].y)*q[j].semn);
j++;
}
else
break;
vechi=v[i].x;
}
for(i=1;i<=m;i++)
{
cout<<xi[i]<<' '<<xs[i]<<' '<<yi[i]<<' '<<ys[i]<<endl;
cout<<raspuns[i]<<'\n';
}
cin.close();
cout.close();
return 0;
}