Cod sursa(job #346126)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 6 septembrie 2009 22:03:27
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <cstdio>   
#include <vector>   
  
using namespace std;   
  
#define file_in "ograzi.in"   
#define file_out "ograzi.out"   
  
#define Nmax 50100   
#define Mod 110937  
  
#define i1 31  
#define i2 67  
  
#define pb push_back   
  
struct coord   
{   
    int x1,y1;   
}p[Nmax],q;   
  
int n,nr,j,xx,yy,w,h,m,px,py;   
vector <unsigned int> c[Mod];   
  
int ok(int c1, int c2)   
{   
    int i,ll,aux;   
    aux=(c1*i1+c2*i2)%Mod; 
    ll=c[aux].size();	
    for (i=0;i<ll;++i)   
    {   
      if ((p[c[aux][i]].x1<=xx) && (xx<=p[c[aux][i]].x1+w)    
        && (p[c[aux][i]].y1<=yy) && (yy<=p[c[aux][i]].y1+h))    
        return 1;      
    }        
    return 0;      
}   
  
int main()   
{   
    int i,aux;   
    char s[20],*pp;  
	freopen(file_in,"r",stdin);   
    freopen(file_out,"w",stdout);   
       
    scanf("%d %d %d %d", &n,&m,&w,&h);   
    for (i=1;i<=n;++i)   
    {   
        //scanf("%d %d", &p[i].x1,&p[i].y1);   
        fgets(s,20,stdin);   
        for (pp=s,p[i].x1=0;'0'<=*pp && *pp<='9';++pp)   
            p[i].x1=p[i].x1*10+*pp-'0';   
        for (pp++,p[i].y1=0;'0'<=*pp && *pp<='9';++pp)   
            p[i].y1=p[i].y1*10+*pp-'0';   

		q.x1=p[i].x1/w;   
        q.y1=p[i].y1/h;   
        aux=(q.x1*i1+q.y1*i2)%Mod;   
        c[aux].pb(i);   
    }   
           
    //sort(p+1,p+n+1,cmp);   
       
    nr=0;   
    for (i=1;i<=m;++i)   
    {   
        //scanf("%d %d", &xx,&yy);   
        //nr+=bs(xx,yy,1,n);   
        fgets(s,20,stdin);   
        for (pp=s,xx=0;'0'<=*pp && *pp<='9';++pp)   
            xx=xx*10+*pp-'0';   
        for (pp++,yy=0;'0'<=*pp && *pp<='9';++pp)   
            yy=yy*10+*pp-'0';   
		px=xx/w;   
        py=yy/h;   
        if (ok(px,py) || ok(px-1,py) || ok(px,py-1) || ok(px-1,py-1))   
            nr++;   
    }   
       
    printf("%d", nr);   
       
       
    fclose(stdin);   
    fclose(stdout);   
       
    return 0;   
}