Cod sursa(job #39534)

Utilizator lucibitLucian Onea lucibit Data 26 martie 2007 20:05:06
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include<stdio.h>
#define maxn 50001
#define maxm 100001
long int n,m,oi[maxm][3],w,h,og[maxm][3],a[maxm][3],y[18][maxm],v[maxm], NR;
void interclaseaza1(long int p, long int q)
{long int k1,k2,a1[maxm],a2[maxm],k,l;
  k=0;
  k1=p;
  l=(p+q)/2;
  k2=l+1;
 while(k1<=l && k2<=q)
 {if(oi[k1][1]<oi[k2][1]){a1[++k]=oi[k1][1];
			  a2[k]=oi[k1][2];
				k1++;}
	 else                 {a1[++k]=oi[k2][1];
			  a2[k]=oi[k2][2];
			  k2++;}
  }
 while (k1<=l) {a1[++k]=oi[k1][1];
			  a2[k]=oi[k1][2];
				k1++;}
 while (k2<=q) {a1[++k]=oi[k2][1];
			  a2[k]=oi[k2][2];
			  k2++;}
 k=0;
 for(k1=p;k1<=q;k1++)
  {oi[k1][1]=a1[++k];
	oi[k1][2]=a2[k];
	 }
 }
void interclaseaza2(long int p, long int q)
{long int k1,k2,a1[maxm],k,l;
  k=0;
  k1=p;
	l=(p+q)/2;
  k2=l+1;
 while(k1<=l && k2<=q)
 {if(v[k1]<v[k2]){a1[++k]=v[k1];
							k1++;}
	 else             {a1[++k]=v[k2];
							  k2++;}
  }
 while (k1<=l) {a1[++k]=v[k1];
				k1++;}
 while (k2<=q) {a1[++k]=v[k2];
						  k2++;}
 k=0;
 for(k1=p;k1<=q;k1++) v[k1]=a1[++k];

 }
void sort1(long int p,long int q)
{if(p!=q) {sort1(p,(p+q)/2);
		sort1((p+q)/2+1,q);
		interclaseaza1(p,q);
		}

  }

 void sort2(long int p, long int q,long int k)
{
 if(p!=q) {long int l=(q+p)/2;
			  sort2(p,l,k+1);
			  sort2(l+1,q,k+1);
			  interclaseaza2 (p,q);
			  for(long int i=p;i<=q;i++) {y[k][i]=v[i];}
			  }
  else {y[k][p]=v[p];}
 }
long int bin (long int k,long int p, long int q, long int a)
{long int l=(p+q)/2;
 if(p!=q) {if(a<=y[k][l]) bin (k,p,l,a);
			  else bin (k,l+1,q,a);
			  }
 else return p;
 }
void interogare(long int k, long int st, long int dr, long int a, long int b,long int i)
{long int l;
 if (st!=dr)
  {if(a<=oi[st][1] && b>=oi[dr][1]) { if((og[i][2]<=y[k][st]) &&(og[i][2]+h>=y[k][dr])) NR+=dr-st+1;
												else if(og[i][2]<=y[k][st]) NR+=bin(k,st,dr,og[i][2]+h)-st;
												 else if(og[i][2]+h>=y[k][dr]) NR+=dr-bin(k,st,dr,og[i][2])+1;
												  else {NR+=bin(k,st,dr,og[i][2]+h)- bin(k,st,dr,og[i][2]);}
											 }
 else {l=(st+dr)/2;
		 if(a<=oi[l][1]) interogare(k+1, st,l, a,b,i);
		 if(b>oi[l][2]) interogare(k+1,l+1,dr,a,b,i);
		  }
  }
  else if(og[i][2]<=y[k][st] && y[k][st]<=og[i][2]+h) NR++;
  }
int main ()
{freopen("ograzi.in","r",stdin);
 scanf("%ld %ld %ld %ld\n",&n,&m,&w,&h);
 long int i,j,x,y;
 for(i=1;i<=n;i++) scanf("%ld %ld\n",&og[i][1],&og[i][2]);
 for(i=1;i<=m;i++) scanf("%ld %ld\n",&oi[i][1],&oi[i][2]);
 sort1(1,m);
 for(i=1;i<=m;i++) v[i]=oi[i][2];
 sort2(1,m,1);
 NR=0;
 for(i=1;i<=n;i++)
 {interogare(1,1,m,og[i][1],og[i][1]+w,i);
  }
 freopen("ograzi.out","w",stdout);
 printf("%ld\n",NR);

 return 0;}