Cod sursa(job #1416378)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 7 aprilie 2015 21:59:50
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;

# define MOD 666013
# define N1 997
int n,m,h,w,dx,dy,nr;
int x,y,key,ok,l   ;

struct _pair{  int x,y;  };
_pair e;
vector<_pair> v[MOD];
char s[100];
void read (int &x, int &y)
{
    x=0; y=0;
    fgets(s+1,100,stdin); l=strlen (s+1);
    int i=1;
    while ('0'<=s[i] && s[i]<='9')
    {
        x=x*10+(s[i]-'0');
        ++i;
    }
    ++i;
    while ('0'<=s[i] && s[i]<='9')
    {
        y=y*10+(s[i]-'0');
        ++i;
    }
}

int main()
{
    freopen("ograzi.in"  , "r"  , stdin );
    freopen("ograzi.out" , "w"  , stdout);

    scanf("%d %d %d %d\n",&n,&m,&w,&h);
    for(int i=1;i<=n;++i){
        read(x,y);
        key= ( (x/w)*N1 + y/h)%MOD;
        e.x=x; e.y=y;
        v[key].push_back(e);
    }
    for(int i=1;i<=m;++i){
        read(x,y);
        ok = 1;
        for(dx= -1; dx <= 0 && ok; ++dx)
            for(dy= -1; dy <= 0 && ok; ++dy ){
                key = ( (x/w +dx )*N1 + y/h + dy ) % MOD;

                if( key < 0 )            continue;
                if( v[key].size() == 0 ) continue;

                for(vector<_pair> :: iterator it = v[key].begin(); it!=v[key].end(); ++it){
                    if( it->x <= x && x <= (it->x + w) )
                        if( it->y <= y && y <= (it->y + h) ){
                            ok = 0;
                            ++nr;
                        }
                }
            }
    }
    printf("%d",nr);


    return 0;
}