Cod sursa(job #26883)

Utilizator AdixSuciu Adrian Adix Data 5 martie 2007 22:13:55
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <stdio.h>
#include <string.h>
long n,m,w,h;
long nroi;
long ogr[50002][3],aux;

void swap(long i,long j){
     

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;
     
     }

long partition(long p,long r,int par){
long i,j,x;
     x=ogr[p][par];
     i=p-1;
     j=r+1;
     do{

           do {j--;} while(ogr[j][par]>x);
           do {i++;} while(ogr[i][par]<x);
           if(i<j) swap(i,j);
              else return j; 
     }while(1);
} 


void quicksort(long p,long r,int par){
     long q;
     if(p<r){ q=partition(p,r,par);
              quicksort(p,q,par);
              quicksort(q+1,r,par);            
            }  
     }
       
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,prim,ultim;
     char aux[1000];
     y=0;x=0;
     in=fopen("ograzi.in","r");
      fscanf(in,"%ld %ld %ld %ld",&n,&m,&w,&h);

			for(i=1;i<=n;i++){
                 fscanf(in,"%ld %ld",&ogr[i][0],&ogr[i][1]);
				  }
			quicksort(1,n,0);
			prim=1;
			for(i=2;i<=n;i++){
                              if(ogr[i-1]!=ogr[i]){ ultim=i-1;
                                                    quicksort(prim,ultim,1);
                                                    prim=ultim+1;}         
                              }

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

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