Cod sursa(job #26669)

Utilizator AdixSuciu Adrian Adix Data 5 martie 2007 20:16:46
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.41 kb
#include <stdio.h>
#include <string.h>
long n,m,w,h;
long nroi;
long ogr[51002][3],aux;
       

void procesare(long x,long y){
     long i;
     for(i=0;i<n;i++){                    
		 if(x>=ogr[i][0]&&x<=ogr[i][0]+w&&y>=ogr[i][1]&&y<=ogr[i][1]+h) {nroi++;break;}
     }
}

void qsort(long l,long r)
  {long i,j,mij,i1,j1;
   i=l;j=r;
   mij=ogr[(i+j)/2][0];
   do{ while(ogr[i][0]<mij) i++;
       while(ogr[j][0]>mij) j--;
       if(i<=j) {if(i<j) {aux=ogr[j][1];
			              ogr[j][1]=ogr[i][1];
			              ogr[j][1]=aux; 
                          aux=ogr[j][0];
			              ogr[j][0]=ogr[i][0];
			              ogr[j][0]=aux; 
                          }
		 i++; j--;}
      }while(i<=j);
   	if(l>j) qsort(l,j);
    if(i<r) qsort(i,r);
}


void bubbles(){
int b,i;
do{b=0;
   for(i=1;i<n;i++){
       if(ogr[i][0]>ogr[i+1][0]) 
                       {aux=ogr[i][0];
                       ogr[i][0]=ogr[i+1][0];
                       ogr[i+1][0]=aux;
                       aux=ogr[i][1];
                       ogr[i][1]=ogr[i+1][1];
                       ogr[i+1][1]=aux;
                       b=1;}
                       }
       }while(b);
}
//INTERSCHIMBARE();
/*void interschimbare(){
     long i,j;
		 for(i=1;i<=n;i++){
				for(j=i+1;j<=n;j++){
				 if(ogr[i][0]>ogr[j][0]){aux=ogr[i][0];
			                     ogr[i][0]=ogr[j][0];
			                     ogr[j][0]=aux; 
                                 aux=ogr[i][1];
			                     ogr[i][1]=ogr[j][1];
			                     ogr[j][1]=aux; 
                                 }
         if(ogr[i][0]==ogr[j][0]&&ogr[i][1]>ogr[j][1]){aux=ogr[i][0];
                                        			  ogr[i][0]=ogr[j][0];
			                                          ogr[j][0]=aux; 
                                                      aux=ogr[i][1];
			                                          ogr[i][1]=ogr[j][1];
			                                          ogr[j][1]=aux; }
                   }
         }
                                             
     }*/

int cautare(long x,long y){
long st,dr,c;
st=1;
dr=n;
while(dr>=st){
c=(dr+st)/2;

if(x>=ogr[dr][0]&&x<=ogr[dr][0]+w) 
    if(y>=ogr[dr][1]&&y<=ogr[dr][1]+h){ return 1;}

if(x>=ogr[st][0]&&x<=ogr[st][0]+w)
		if(y>=ogr[st][1]&&y<=ogr[st][1]+h){ return 1;}


if(x<ogr[c][0]){ dr=c-1;continue;}
if(x>ogr[c][0]+w){ st=c+1;continue;}
if(x>=ogr[c][0]&&x<=ogr[c][0]+w){
		if(y<ogr[c][1]){ dr=c-1;continue;}
		if(y>ogr[c][1]+h){ st=c+1;continue;}
		if(y>=ogr[c][1]&&y<=ogr[c][1]+h){ return 1;}
if(dr==st) return 0;
    }
}
return 0;
}

    

void citire(){
     FILE *in;
     long i,x,y;
     char aux[1000];
     
     in=fopen("ograzi.in","r");
//      fgets(aux,1000,in);
      fscanf(in,"%ld %ld %ld %ld",&n,&m,&w,&h);

			for(i=1;i<=n;i++){
                 fgets(aux,1000,in);              
				 fscanf(in,"%ld %ld",&ogr[i][0],&ogr[i][1]);
	  										 }
      qsort(1,n);
 //     bubbles();

//interschimbare();
			for(i=1;i<=m;i++){
                       fscanf(in,"%ld %ld",&x,&y);
                       nroi=nroi+cautare(x,y);
//                         procesare(x,y);
                       }
     
     }

void scriere(){
     FILE *out;
     out=fopen("ograzi.out","w");
     fprintf(out,"%ld",nroi);     
     }
     
int main(){
     citire();
     scriere();
return 0;
     }