Cod sursa(job #6778)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 20 ianuarie 2007 22:27:47
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include<stdio.h>
#define fin  "zoo.in"
#define fout "zoo.out"
#define Nmax 1600
int v[Nmax][2],oy[10*Nmax][2],viz[Nmax];
int n,m,ax,bx,ay,by,segm[10*Nmax][2];
int free,sol,lim_lo,lim_hi;
FILE *in,*out;

void qsort(int st,int dr,int p,int vec[Nmax][2]) {
int i,j,m;	
	i=st; j=dr;
	m=vec[(i+j)/2][p];

	do {
		while (vec[i][p]<m) ++i;
		while (vec[j][p]>m) --j;
		if (i<=j) {
			int aux;
			aux=vec[i][0]; vec[i][0]=vec[j][0]; vec[j][0]=aux;
			aux=vec[i][1]; vec[i][1]=vec[j][1]; vec[j][1]=aux;
			++i; --j;
		}
	
	} while (i<j);

	if (i<dr) qsort(i,dr,p,vec);
	if (j>st) qsort(st,j,p,vec);

}

void build(int nod,int st,int dr) {
int i,m;
	
	//printf("\nNod %i:\n",nod);

	//for (i=segm[nod][0];i<=segm[nod][1];++i)
	//       printf("%i %i\n",oy[i][0],oy[i][1]);

	m=(st+dr)/2;
	
	if (st==dr) return ;

	segm[2*nod][0]=free+1;

	for (i=segm[nod][0];i<=segm[nod][1];++i) {
	       	viz[i]=0;	
	
		if (v[st][0]<=oy[i][0] && oy[i][0]<=v[m][0]) {
			
			oy[++free][0]=oy[i][0];
			oy[free][1]=oy[i][1];	
			viz[i]=1;
		}
	}
	segm[2*nod][1]=free;

	segm[2*nod+1][0]=free+1;

	for (i=segm[nod][0];i<=segm[nod][1];++i) 
	
		if (!viz[i] && v[m+1][0]<=oy[i][0] && oy[i][0]<=v[dr][0]) {
			
			oy[++free][0]=oy[i][0];
			oy[free][1]=oy[i][1];	
		}
	
	segm[2*nod+1][1]=free;

	build(2*nod,st,m);
	build(2*nod+1,m+1,dr);

}

int s_lo(int st,int dr) {
int m;
	if (st>dr) return -1;

	m=(st+dr)/2;
	if (oy[m][1]>=ay) {
		if (oy[m-1][1]>=ay && m-1>=lim_lo) return s_lo(st,m-1);

		else return m;
	}
	else return s_lo(m+1,dr);
}

int s_hi(int st,int dr) {
int m;
	if (st>dr) return -1;

	m=(st+dr)/2;
	if (oy[m][1]<=by) {
		if (oy[m+1][1]<=by && m+1<=lim_hi) return s_hi(m+1,dr);

		else return m;
	}
	else return s_hi(st,m-1);

}

void query(int nod,int st,int dr) {
int m,p1,p2;
	if (ax<=v[st][0] && v[dr][0]<=bx) {
		
		//printf("\n%i %i",st,dr);
		lim_lo=segm[nod][0];
		lim_hi=segm[nod][1];
		p1=s_lo(segm[nod][0],segm[nod][1]);
		p2=s_hi(segm[nod][0],segm[nod][1]);

		//printf(" %i %i",p1,p2);

		if (p1!=-1 && p2!=-1) sol+=p2-p1+1;
	}

	else {
		m=(st+dr)/2;
		if (ax<=v[m][0]) query(2*nod,st,m);
		if (bx>v[m][0]) query(2*nod+1,m+1,dr);

	}
}

int main() {
int i;
	in=fopen(fin,"r"); out=fopen(fout,"w");

	fscanf(in,"%i",&n);
	for (i=1;i<=n;++i) {
		fscanf(in,"%i%i",&v[i][0],&v[i][1]);
		oy[i][0]=v[i][0];
		oy[i][1]=v[i][1];
	}

	qsort(1,n,0,v);

	//for (i=1;i<=n;++i) printf("%i %i\n",v[i][0],v[i][1]);
	
	qsort(1,n,1,oy);
	
	free=n; segm[1][0]=1; segm[1][1]=free;
	
	//printf("Tree:\n");	
	build(1,1,n);
	
	fscanf(in,"%i",&m);
	for (i=1;i<=m;++i) { 
		
		fscanf(in,"%i%i%i%i",&ax,&ay,&bx,&by);

		sol=0;

		query(1,1,n);
	
		fprintf(out,"%i\n",sol);
	}

	fclose(in);
	fclose(out);

	return 0;

}