Cod sursa(job #74600)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 26 iulie 2007 15:04:44
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.9 kb
#include<stdio.h>
struct nodl{

	long int ind;
	nodl *next;
};
struct nod{

	long int nr;
	long int xmin;long int xmax;
	long int ymin;long int ymax;
	nodl *p;
	nodl *u;
	nod *s1;
	nod *s2;
	nod *s3;
	nod *s4;
};
long int n,i,m,x0min,x0max,y0min,y0max,sol,x[16001],y[16001];
nod *arb;
void pune(nod *aa,long int ii);
void prel(nod *aa);
long int calc(nod *aa,long int xx,long int xxx,long int yy,long int yyy);
int main()
{
	FILE *f,*g;
	f=fopen("zoo.in","r");
	g=fopen("zoo.out","w");
	fscanf(f,"%ld",&n);
	for(i=1;i<=n;i++)
	 fscanf(f,"%ld%ld",&x[i],&y[i]);
	arb=new nod;
	arb->nr=0;arb->xmin=-2000000000;arb->xmax=2000000001;
	arb->ymin=-2000000000;arb->ymax=2000000001;
	arb->p=0;arb->u=0;arb->s1=0;arb->s2=0;arb->s3=0;arb->s4=0;
	for(i=1;i<=n;i++)
	 pune(arb,i);
	prel(arb);
	fscanf(f,"%ld",&m);
	for(i=1;i<=m;i++)
	{ fscanf(f,"%ld%ld%ld%ld",&x0min,&y0min,&x0max,&y0max);
	  x0max++;y0max++;
	  sol=calc(arb,x0min,x0max,y0min,y0max);
	  fprintf(g,"%ld\n",sol);
	}
	fcloseall();
	return 0;
}
void pune(nod *aa,long int ii)
{
	nodl *pp;
	pp=new nodl;
	pp->ind=ii;pp->next=0;aa->nr++;
	if(!aa->p){aa->p=pp;aa->u=pp;}
	else{aa->u->next=pp;aa->u=pp;}
}
void prel(nod *aa)
{       long int xmed,ymed,iii;
	nodl *qq;
	if(!aa->nr) return;
	if(aa->xmax<=aa->xmin+1)
	 if(aa->ymax<=aa->ymin+1)
	  return;
	aa->s1=new nod;aa->s2=new nod;aa->s3=new nod;aa->s4=new nod;
	xmed=(aa->xmax+aa->xmin)/2;
	ymed=(aa->ymax+aa->ymin)/2;
	aa->s1->nr=0;aa->s2->nr=0;aa->s3->nr=0;aa->s4->nr=0;
	aa->s1->xmin=xmed;aa->s1->xmax=aa->xmax;
	aa->s1->ymin=ymed;aa->s1->ymax=aa->ymax;
	aa->s2->xmin=aa->xmin;aa->s2->xmax=xmed;
	aa->s2->ymin=ymed;aa->s2->ymax=aa->ymax;
	aa->s3->xmin=aa->xmin;aa->s3->xmax=xmed;
	aa->s3->ymin=aa->ymin;aa->s3->ymax=ymed;
	aa->s4->xmin=xmed;aa->s4->xmax=aa->xmax;
	aa->s4->ymin=aa->ymin;aa->s4->ymax=ymed;
	aa->s1->p=0;aa->s1->u=0;
	aa->s1->s1=0;aa->s1->s2=0;
	aa->s1->s3=0;aa->s1->s4=0;
	aa->s2->p=0;aa->s2->u=0;
	aa->s2->s1=0;aa->s2->s2=0;
	aa->s2->s3=0;aa->s2->s4=0;
	aa->s3->p=0;aa->s3->u=0;
	aa->s3->s1=0;aa->s3->s2=0;
	aa->s3->s3=0;aa->s3->s4=0;
	aa->s4->p=0;aa->s4->u=0;
	aa->s4->s1=0;aa->s4->s2=0;
	aa->s4->s3=0;aa->s4->s4=0;
	while(aa->p)
	{ iii=aa->p->ind;
	  if(y[iii]>=ymed)
	   { if(x[iii]>=xmed)  pune(aa->s1,iii);
	     else  pune(aa->s2,iii);
	   }
	  else
	   { if(x[iii]<xmed) pune(aa->s3,iii);
	     else pune(aa->s4,iii);
	   }
	  qq=aa->p;
	  aa->p=aa->p->next;
	  delete qq;
	}
	if(aa->s1->nr) prel(aa->s1); else (aa->s1=0);
	if(aa->s2->nr) prel(aa->s2); else (aa->s2=0);
	if(aa->s3->nr) prel(aa->s3); else (aa->s3=0);
	if(aa->s4->nr) prel(aa->s4); else (aa->s4=0);
}
long int calc(nod *aa,long int xx,long int xxx,long int yy,long int yyy)
{
	long int ret,ret1,ret2,ret3,ret4;
	if(!aa) return 0;
	if(xxx<=aa->xmin) return 0;
	if(xx>=aa->xmax) return 0;
	if(yyy<=aa->ymin) return 0;
	if(yy>=aa->xmax) return 0;
	if(xx<aa->xmin) { ret=calc(aa,aa->xmin,xxx,yy,yyy);return ret;}
	if(xxx>aa->xmax) { ret=calc(aa,xx,aa->xmax,yy,yyy);return ret;}
	if(yy<aa->ymin) { ret=calc(aa,xx,xxx,aa->ymin,yyy);return ret;}
	if(yyy>aa->ymax) { ret=calc(aa,xx,xxx,yy,aa->ymax);return ret;}
	if(xx>aa->xmin) {ret1=calc(aa->s1,xx,xxx,yy,yyy);
	ret2=calc(aa->s2,xx,xxx,yy,yyy);ret3=calc(aa->s3,xx,xxx,yy,yyy);
	ret4=calc(aa->s4,xx,xxx,yy,yyy);ret=ret1+ret2+ret3+ret4;return ret;}
	if(xxx<aa->xmax) {ret1=calc(aa->s1,xx,xxx,yy,yyy);
	ret2=calc(aa->s2,xx,xxx,yy,yyy);ret3=calc(aa->s3,xx,xxx,yy,yyy);
	ret4=calc(aa->s4,xx,xxx,yy,yyy);ret=ret1+ret2+ret3+ret4;return ret;}
	if(yy>aa->ymin) {ret1=calc(aa->s1,xx,xxx,yy,yyy);
	ret2=calc(aa->s2,xx,xxx,yy,yyy);ret3=calc(aa->s3,xx,xxx,yy,yyy);
	ret4=calc(aa->s4,xx,xxx,yy,yyy);ret=ret1+ret2+ret3+ret4;return ret;}
	if(yyy<aa->ymax) {ret1=calc(aa->s1,xx,xxx,yy,yyy);
	ret2=calc(aa->s2,xx,xxx,yy,yyy);ret3=calc(aa->s3,xx,xxx,yy,yyy);
	ret4=calc(aa->s4,xx,xxx,yy,yyy);ret=ret1+ret2+ret3+ret4;return ret;}
	return aa->nr;
}