Cod sursa(job #1023857)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 7 noiembrie 2013 20:07:33
Problema Ograzi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#define point pair <int, int>
#define x first
#define y second

using namespace std;

const int MOD = 666013;

vector <point> myHash[MOD];

int hash(point X) {
    return (X.x + 6971 * X.y) % MOD;
}

int H, W;

bool is(point X, int where) {
    vector <point> :: iterator it;
    if (where < 0)
        return 0;
    for (it = myHash[where].begin(); it != myHash[where].end(); ++it)
        if ((*it).x <= X.x && X.x <= (*it).x + W &&
            (*it).y <= X.y && X.y <= (*it).y + H)
                return 1;
    return 0;
}

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

    int N, M;
    scanf("%d%d%d%d", &N, &M, &W, &H);
    for (int i = 1; i <= N; ++i) {
        point tmp;
        scanf("%d%d", &tmp.x, &tmp.y);
        myHash[hash(make_pair(tmp.x / W, tmp.y / H))].push_back(tmp);
    }

    int sol = 0;
    for (int i = 1; i <= M; ++i) {
        point tmp;
        scanf("%d%d", &tmp.x, &tmp.y);
        bool ok = 0;
        for (int dx = -1; dx <= 0 && !ok; ++dx)
            for (int dy = -1; dy <= 0 && !ok; ++dy)
                ok = is(tmp, hash(make_pair(tmp.x / W + dx, tmp.y / H + dy)));
        sol += ok;
    }

    printf("%d", sol);
    return 0;
}