Cod sursa(job #27592)

Utilizator SebbySebastian Sebby Data 6 martie 2007 15:39:12
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
typedef struct el{long int x,y;}EL;
long int nr=0,n,m,h,w1; EL w[100001],v[50001];
void citire()
{long int i; FILE *f;
 f=fopen("ograzi.in","r");
 fscanf(f,"%ld %ld %ld %ld",&n,&m,&w1,&h);
 for(i=1;i<=n;i++)
   fscanf(f,"%ld %ld",&v[i].x,&v[i].y);
 for(i=1;i<=m;i++)
   fscanf(f,"%ld %ld",&w[i].x,&w[i].y);
 fclose(f);
}
void quicksort1(long l,long r)
{long i,j,x; EL aux;
 i=l; j=r; x=v[(i+j)/2].x;
 do{while(v[i].x<x) i++;
    while(v[j].x>x) j--;
    if(i<=j){ if(i<j) {aux=v[i];
		       v[i]=v[j];
		       v[j]=aux;}
	      i++; j--;
	    }
   }while(i<=j);
 if(l<j) quicksort1(l,j);
 if(i<r) quicksort1(i,r);
}
void quicksort2(long l,long r)
{long i,j,x; EL aux;
 i=l; j=r; x=w[(i+j)/2].x;
 do{while(w[i].x<x) i++;
    while(w[j].x>x) j--;
    if(i<=j){ if(i<j) {aux=w[i];
		       w[i]=w[j];
		       w[j]=aux;}
	      i++; j--;
	    }
   }while(i<=j);
 if(l<j) quicksort2(l,j);
 if(i<r) quicksort2(i,r);
}
void oi()
{long i,j=1,b,c=0,k; FILE *g;
 for(i=1;i<=m;i++)
   if(i>1&&(w[i].x==w[i-1].x)&&(w[i].y==w[i-1].y&&c)) nr++;
     else {b=1; c=0; k=j-1; j=0;
	  while(b!=0&&j<=n-k)
	    {if((w[i].x>=v[j+k].x)&&(w[i].x<=v[j+k].x+w1)&&(w[i].y>=v[j+k].y)&&(w[i].y<=v[j+k].y+h)){nr++; b=0; c=1;
												     if(j==0) j++;}
	     else j++;}
	 }
 g=fopen("ograzi.out","w");
 fprintf(g,"%ld",nr);
 fcloseall();
}
int main()
{citire();
 quicksort1(1,n);
 quicksort2(1,m);
 oi();
 return 0;
}