Cod sursa(job #326892)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 26 iunie 2009 15:39:26
Problema Ograzi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <cstdio>   
#include <vector>   
  
using namespace std;   
  
#define file_in "ograzi.in"   
#define file_out "ograzi.out"   
  
#define Nmax 50100   
#define Mod 666013  
  
#define i1 199  
#define i2 211  
  
#define pb push_back   
  
struct coord   
{   
    int x1,y1;   
}p[Nmax],q;   
  
int n,nr,j,xx,yy,w,h,m,aux,px,py;   
vector<unsigned short> c[Mod];   
  
bool cmp(coord a, coord b)   
{   
    return (a.x1<b.x1);   
}   
  
int bs(int xx,int yy,int ls, int ld)   
{   
    int mij;   
       
    while(ls<=ld)   
    {   
        mij=(ls+ld)>>1;   
           
        if ((xx>=p[mij].x1 && xx<=p[mij].x1+w) &&   
            (yy>=p[mij].y1 && yy<=p[mij].y1+h))   
            return 1;   
        else  
        if (xx<=p[mij].x1 || yy<=p[mij].y1)   
            return bs(xx,yy,ls,mij-1);   
        else  
        if (xx>=p[mij].x1+w || yy>=p[mij].y1+h)   
            return bs(xx,yy,mij+1,ld);   
    }   
       
    return 0;   
}   
  
int ok(int c1, int c2)   
{   
    int i,ll;   
    aux=(c1*i1+c2*i2)%Mod;   
    for (i=0;i<c[aux].size();++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;   
    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;   
}