Cod sursa(job #1002184)

Utilizator poptibiPop Tiberiu poptibi Data 26 septembrie 2013 23:11:44
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <vector>
using namespace std;

const int V = 123457, MOD = 666013, NMAX = 50005, CMAX = 8192;
const int DX[] = {-1, 0, -1, 0}, DY[] = {0, -1, -1, 0};

int N, M, W, H, X[NMAX], Y[NMAX], Ans;
vector<int> Hash[MOD];
char Buf[CMAX];
int Ptr;

int GetInt()
{
    int Ans = 0;
    while(!isdigit(Buf[Ptr]))
        if(++ Ptr >= CMAX)
            fread(Buf, 1, CMAX, stdin), Ptr = 0;
    while(isdigit(Buf[Ptr]))
    {
        Ans = Ans * 10 + Buf[Ptr] - '0';
        if(++ Ptr >= CMAX)
            fread(Buf, 1, CMAX, stdin), Ptr = 0;
    }
    return Ans;
}

int main()
{
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    fread(Buf, 1, CMAX, stdin);
    
    N = GetInt();
    M = GetInt();
    W = GetInt();
    H = GetInt();
    for(int i = 1; i <= N; ++ i)
    {
        X[i] = GetInt();
        Y[i] = GetInt();
        int Key = (1LL * (X[i] / W) * V + (Y[i] / H)) % MOD;
        Hash[Key].push_back(i);
    }
    
    for(int i = 1; i <= M; ++ i)
    {
        int Xq, Yq;
        
        Xq = GetInt();
        Yq = GetInt();
        
        bool Found = 0;
        
        for(int j = 0; j < 4 && !Found; ++ j)
        {
            if(Xq / W + DX[j] < 0 || Yq / H + DY[j] < 0) continue;
            
            int Key = (1LL * (Xq / W + DX[j]) * V + (Yq / H + DY[j])) % MOD;
            
            for(vector<int> :: iterator it = Hash[Key].begin(); it != Hash[Key].end(); ++ it)
                if(X[*it] <= Xq && Xq <= X[*it] + W && Y[*it] <= Yq && Yq <= Y[*it] + H)
                {
                    Found = 1;
                    break;
                }
        }
        
        Ans += Found;
    }
    
    printf("%i\n", Ans);
    return 0;
}