Cod sursa(job #49244)

Utilizator moga_florianFlorian MOGA moga_florian Data 5 aprilie 2007 16:56:47
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.25 kb
#include<stdio.h>
#define L 1000010
#define cst 1000003

struct nod{int x,y,xi,yi;nod* next;};
typedef nod* list;
list a[L],aux;


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,hv;
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)
     {
     hv=nx*1000+ny;
     hv%=cst;
     
     if(a[hv]==NULL)
        {
        a[hv]=new nod;
        a[hv]->next=NULL;
        }
     else
        {
        aux=new nod;
        aux->next=a[hv];
        a[hv]=aux;                         
        }     
     a[hv]->x=nx;
     a[hv]->y=ny;
     a[hv]->xi=ix;
     a[hv]->yi=iy;
     }
     
  nx+=W;
  if(ix<=nx && nx<=ix+W && iy<=ny && ny<=iy+H)
     {
       hv=nx*1000+ny;
  hv%=cst;
     if(a[hv]==NULL)
        {
        a[hv]=new nod;
        a[hv]->next=NULL;
        }
     else
        {
        aux=new nod;
        aux->next=a[hv];
        a[hv]=aux;                         
        }     
     a[hv]->x=nx;
     a[hv]->y=ny;
     a[hv]->xi=ix;
     a[hv]->yi=iy;
     }
  
  ny+=H;
  if(ix<=nx && nx<=ix+W && iy<=ny && ny<=iy+H)
     {
       hv=nx*1000+ny;
  hv%=cst;
     if(a[hv]==NULL)
        {
        a[hv]=new nod;
        a[hv]->next=NULL;
        }
     else
        {
        aux=new nod;
        aux->next=a[hv];
        a[hv]=aux;                         
        }     
     a[hv]->x=nx;
     a[hv]->y=ny;     
     a[hv]->xi=ix;
     a[hv]->yi=iy;
     }

  nx-=W;
  if(ix<=nx && nx<=ix+W && iy<=ny && ny<=iy+H)
     {
       hv=nx*1000+ny;
  hv%=cst;
     if(a[hv]==NULL)
        {
        a[hv]=new nod;
        a[hv]->next=NULL;
        }
     else
        {
        aux=new nod;
        aux->next=a[hv];
        a[hv]=aux;                         
        }     
     a[hv]->x=nx;
     a[hv]->y=ny;
     a[hv]->xi=ix;
     a[hv]->yi=iy;
     } 
  }
      
int sol=0,t;
for(i=1;i<=M;i++)
  {
  fscanf(fin,"%d%d",&ix,&iy);
  t=0;
  
  if(ix%W)
    nx=ix-(ix%W);
  else
    nx=ix;
    
  if(iy%H)
    ny=iy-(iy%H);  
  else
    ny=iy;  
    
  hv=nx*1000+ny;
  hv%=cst;
  aux=a[hv];
  while(aux && !(aux->x==nx && aux->y==ny) ) aux=aux->next;
  if(aux)
    if(aux->xi<=ix && ix<=aux->xi+W && aux->yi<=iy && iy<=aux->yi+H)
        t=1;

  nx+=W;
  hv=nx*1000+ny;
  hv%=cst;
  aux=a[hv];
  while(aux && !(aux->x==nx && aux->y==ny) ) aux=aux->next;
  if(aux)
    if(aux->xi<=ix && ix<=aux->xi+W && aux->yi<=iy && iy<=aux->yi+H)
        t=1;
        
  ny+=H;
  hv=nx*1000+ny;
  hv%=cst;
  aux=a[hv];
  while(aux && !(aux->x==nx && aux->y==ny) ) aux=aux->next;
  if(aux)
    if(aux->xi<=ix && ix<=aux->xi+W && aux->yi<=iy && iy<=aux->yi+H)
        t=1;
        
  nx-=W;
  hv=nx*1000+ny;
  hv%=cst;
  aux=a[hv];
  while(aux && !(aux->x==nx && aux->y==ny) ) aux=aux->next;
  if(aux)
    if(aux->xi<=ix && ix<=aux->xi+W && aux->yi<=iy && iy<=aux->yi+H)
        t=1;
        
  sol+=t;
  }        
  
fprintf(fout,"%d\n",sol);
fclose(fin);
fclose(fout);
return 0;
}