Cod sursa(job #1067445)

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

using namespace std;

const int MAX = 100050;
const int MOD = 68713;
const int FIRST = 7793;
const int SECOND = 1000000003;
const int BUFF_MAX = (1 << 20);

int N, M, H, W, ans, poz;

char Buff[BUFF_MAX];

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;
}

inline int getInt() {
    while(Buff[poz] < '0' || Buff[poz] > '9') 
        if(++poz == BUFF_MAX) {
            fread(Buff, 1, BUFF_MAX, stdin);
            poz = 0;
        }
    int ans = 0;
    while(Buff[poz] >= '0' && Buff[poz] <= '9') {
        ans = ans * 10 + Buff[ poz++ ] - '0';
        if(poz == BUFF_MAX) {
            fread(Buff, 1, BUFF_MAX, stdin);
            poz = 0;
        }
    } return ans;
}

int main() {
    freopen("ograzi.in", "r", stdin);
    fread(Buff, 1, BUFF_MAX, stdin);

    N = getInt();
    M = getInt();
    W = getInt();
    H = getInt();

    for(int i = 0; i < N; i++) {
        V[i].x = getInt();
        V[i].y = getInt();

        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++) {
        P.x = getInt();
        P.y = getInt();

        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);
}