Cod sursa(job #1067438)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 26 decembrie 2013 20:26:35
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <vector>

using namespace std;

const int MAX = 100050;
const int MOD = 666013;
const int FIRST = 7793;
const int SECOND = 1000000003;

int N, M, H, W, ans;

pair<int, int> V[MAX], P;
#define x first
#define y second

vector<int> Hash[MOD];

bool Ok(const pair<int, int> &D, const pair<int, int> &P) {
    if(D.x <= P.x && P.x <= D.x + W && D.y <= P.y && P. y <= D.y + H) 
        return true;
    return false;
}

inline int getHashKey(int X, int Y) {
    X /= W; Y /= H;
    X %= MOD, Y %= MOD;
    return (1LL * X * FIRST + 1LL * Y * SECOND) % MOD;
}

int main() {
    freopen("ograzi.in", "r", stdin);
    
    scanf("%d %d %d %d\n", &N, &M, &W, &H);

    for(int i = 0; i < N; i++) {
        scanf("%d %d\n", &V[i].x, &V[i].y);
        Hash[ getHashKey(V[i].x, V[i].y) ].push_back(i);
        Hash[ getHashKey(V[i].x + W, V[i].y) ].push_back(i);
        Hash[ getHashKey(V[i].x, V[i].y + H) ].push_back(i);
        Hash[ getHashKey(V[i].x + W, V[i].y + H) ].push_back(i);
    }

    for(int i = 0; i < M; i++) {
        scanf("%d %d\n", &P.x, &P.y);
        int HashKey = getHashKey(P.x, P.y);
        for(size_t j = 0; j < Hash[ HashKey ].size(); j++) {
            if(Ok(V[ Hash[HashKey][j] ], P)) {
                ans++;
                break;
            }
        }
    }
    
    fclose(stdin);

    freopen("ograzi.out", "w", stdout);
    printf("%d\n", ans);
    fclose(stdout);
}