Cod sursa(job #1416376)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 7 aprilie 2015 21:56:39
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 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   ;

struct _pair{  int x,y;  };
_pair e;
vector<_pair> v[MOD];

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

    scanf("%d %d %d %d",&n,&m,&w,&h);
    for(int i=1;i<=n;++i){
        scanf("%d %d",&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){
        scanf("%d %d",&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;
}