Cod sursa(job #49161)

Utilizator moga_florianFlorian MOGA moga_florian Data 5 aprilie 2007 14:53:06
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include<stdio.h>
#define L 200010

int x[L],y[L],np=0;

int search(int ix,int iy)
{
int li,lf,m;
li=1;
lf=np;

while(li<=lf)
 {
 m=(li+lf)>>1;
 if(x[m]==ix && y[m]==iy)
    return 1;
 if(x[m]<ix || (x[m]==ix && y[m]<iy) )            
    li=m+1;
 else
    lf=m-1;
 }
return 0;
}

int main()
{
FILE *fin=fopen("ograzi.in","r"),
     *fout=fopen("ograzi.out","w");
     
int N,M,H,W,i,ix,iy,nx,ny,j,k;
fscanf(fin,"%d%d%d%d",&N,&M,&W,&H);

for(i=1;i<=N;i++)
  {
  fscanf(fin,"%d%d",&ix,&iy);
  
  if(ix%W)
    nx=ix-(ix%W)+W;
  else
    nx=ix;
    
  if(iy%H)
    ny=iy-(iy%H)+H;  
  else
    ny=iy;  
    
  if(ix<=nx && nx<=ix+W && iy<=ny && ny<=iy+H)
     {
     x[++np]=nx;
     y[np]=ny;
     }
     
  nx+=W;
  if(ix<=nx && nx<=ix+W && iy<=ny && ny<=iy+H)
     {
     x[++np]=nx;
     y[np]=ny;
     }
  
  ny+=H;
  if(ix<=nx && nx<=ix+W && iy<=ny && ny<=iy+H)
     {
     x[++np]=nx;
     y[np]=ny;
     }

  nx-=W;
  if(ix<=nx && nx<=ix+W && iy<=ny && ny<=iy+H)
     {
     x[++np]=nx;
     y[np]=ny;
     } 
  }
      
//sort
for(i=1;i<=np;i++)
  {
  j=i;
  while(j/2 && (x[j/2]<x[j] || (x[j/2]==x[j] && y[j/2]<y[j])))
     {
     x[j/2]^=x[j];
     x[j]^=x[j/2];
     x[j/2]^=x[j];
     
     y[j/2]^=y[j];
     y[j]^=y[j/2];
     y[j/2]^=y[j];
     
     j/=2;
     }                
  }
  
i=np;
while(i>1)
 {
 x[1]^=x[i];
 x[i]^=x[1];
 x[1]^=x[i];
 
 y[1]^=y[i];
 y[i]^=y[1];
 y[1]^=y[i];
 i--;
 
 j=1;
 while(1)
  {
  k=j<<1;
  if(k>i) break;
  if(k+1<=i && (x[k+1]>x[k] || (x[k+1]==x[k] && y[k+1]>y[k])) ) k++;       
  if(x[j]>=x[k] || (x[j]==x[k] && y[j]>=y[k])) break;
  
  x[j]^=x[k];
  x[k]^=x[j];
  x[j]^=x[k];
  
  y[j]^=y[k];
  y[k]^=y[j];
  y[j]^=y[k];
  
  j=k;  
  }         
 }
      
int sol=0;
for(i=1;i<=M;i++)
  {
  fscanf(fin,"%d%d",&ix,&iy);
  
  if(ix%W)
    nx=ix-(ix%W)+W;
  else
    nx=ix;
    
  if(iy%H)
    ny=iy-(iy%H)+H;  
  else
    ny=iy;  
    
  if(search(nx,ny))
     sol++;               
  else
    {
    nx+=W;
    if(search(nx,ny))
       sol++;
    else
      {
      ny+=H;
      if(search(nx,ny))
         sol++;
      else
        {
        nx-=W;       
        if(search(nx,ny))
           sol++;
        }       
      }                      
    }
  }        
  
fprintf(fout,"%d\n",sol);
fclose(fin);
fclose(fout);
return 0;
}