Cod sursa(job #82449)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 6 septembrie 2007 23:16:17
Problema Ograzi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

#define maxn 50010
#define mod 1109//3749
#define b1 31
#define b2 67
#define maxl 15
#define pb push_back

int n,m,x,y,sol,l,X,Y;
int a[maxn],b[maxn];
vector <unsigned short> c[mod];
char v[maxl];

inline int check(int px,int py)
{
    int i,aux;
    aux=(px*b1+py*b2)%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("ograzi.in","r",stdin);
    freopen("ograzi.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(v,maxl,stdin);
        l=strlen(v)-2;
        
        for (j=0;v[j]!=' ';j++) a[i]=a[i]*10+v[j]-'0';
        for (j++;j<=l;j++) b[i]=b[i]*10+v[j]-'0';
        
        px=a[i]/x;
        py=b[i]/y;
        
        aux=(px*b1+py*b2)%mod;
        c[aux].pb(i); 
    }
    
    for (i=1;i<=m;i++)
    {
        fgets(v,maxl,stdin);
        l=strlen(v)-2;
        
        X=Y=0;
        for (j=0;v[j]!=' ';j++) X=X*10+v[j]-'0';
        for (j++;j<=l;j++) Y=Y*10+v[j]-'0';
        
        px=X/x;
        py=Y/y;
        
        if (check(px,py) || (check(px-1,py)) || (check(px,py-1)) || (check(px-1,py-1))) sol++;
    }
    
    printf("%d\n",sol);
    
    return 0;
}