Cod sursa(job #346133)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 6 septembrie 2009 22:26:51
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define file_in "ograzi.in"
#define file_out "ograzi.out"

#define Nmax 50010
#define Mod 110937
#define i1 31
#define i2 67

#define pb push_back

int n,m,x,y,nr,l,X,Y;
int a[Nmax],b[Nmax];
vector <unsigned short> c[Mod];
char s[20];

inline int ok(int px,int py)
{
    int i,aux;
    aux=(px*i1+py*i2)%Mod;
    l=c[aux].size();
    for (i=0;i<l;++i)
      if ((a[c[aux][i]]<=X) && (X<=a[c[aux][i]]+x) && (b[c[aux][i]]<=Y) && (Y<=b[c[aux][i]]+y)) 
		  return 1;
      
    return 0;
}

int main()
{
    freopen(file_in,"r",stdin);
    freopen(file_out,"w",stdout);
    
    scanf("%d %d %d %d ",&n,&m,&x,&y);
    
    int i,j,px,py,aux;
    
    for (i=1;i<=n;++i)
    {
        fgets(s,20,stdin);
		l=strlen(s)-2;   
        for (j=0;s[j]!=' ';++j) 
			a[i]=a[i]*10+s[j]-'0';
        for (j++;j<=l;++j) 
			b[i]=b[i]*10+s[j]-'0';
        
        px=a[i]/x;
        py=b[i]/y;
        
        aux=(px*i1+py*i2)%Mod;
        c[aux].pb(i); 
    }
    
    for (i=1;i<=m;++i)
    {
        fgets(s,20,stdin);
		l=strlen(s)-2;
        X=Y=0;
        for (j=0;s[j]!=' ';++j) 
			X=X*10+s[j]-'0';
        for (j++;j<=l;++j) 
			Y=Y*10+s[j]-'0';
        
        px=X/x;
        py=Y/y;
        
        if (ok(px,py) || (ok(px-1,py)) || (ok(px,py-1)) || (ok(px-1,py-1))) nr++;
    }
    
    printf("%d\n",nr);
	
	fclose(stdin);
	fclose(stdout);
    
    return 0;
}