Cod sursa(job #6803)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 20 ianuarie 2007 23:18:10
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include<stdio.h>
#define fin  "zoo.in"
#define fout "zoo.out"
#define Nmax 160000
int v[Nmax][2],oy[Nmax][2];
int n,m,ax,bx,ay,by,segm[Nmax][2];
int last,sol,lim_lo,lim_hi;

void qsort1(int st,int dr) {
int i,j,m;	
	i=st; j=dr;
	m=v[(i+j)/2][0];

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

	if (i<dr) qsort1(i,dr);
	if (j>st) qsort1(st,j);

}

void qsort2(int st,int dr) {
int i,j,m;	
	i=st; j=dr;
	m=oy[(i+j)/2][1];

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

	if (i<dr) qsort2(i,dr);
	if (j>st) qsort2(st,j);

}


void build(int nod,int st,int dr) {
int i,m;
char viz[Nmax];
	//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]=last+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[++last][0]=oy[i][0];
			oy[last][1]=oy[i][1];	
			viz[i]=1;
		}
	}
	segm[2*nod][1]=last;

	segm[2*nod+1][0]=last+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[++last][0]=oy[i][0];
			oy[last][1]=oy[i][1];	
		}
	
	segm[2*nod+1][1]=last;

	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;
FILE *in,*out;
	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];
	}

	qsort1(1,n);
	qsort2(1,n);

	/*last=n; segm[1][0]=1; segm[1][1]=last;
	
	//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;

}