Cod sursa(job #1020969)

Utilizator ericptsStavarache Petru Eric ericpts Data 2 noiembrie 2013 22:11:53
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <cstdio>
#include <vector>
#include <utility>

using namespace std;

char buff[1<<15];
char * at = buff;
const int MOD = 66013;

int n,m;
int w,h;

const int dx[] = {1, 0, -1};
const int dy[] = {1, 0, -1};

vector< pair<int, int> > hsh[MOD];

inline int key(const int x, const int y){
    return (1LL * x * x * h + y * 3) % MOD;
}

void insert(const int x, const int y){
    const int chain = key(x/w, y/h);
    hsh[chain].push_back(make_pair(x, y));
}

bool search(const int x, const int y){
    for(int i = 0 ; i < 3 ; ++i)for(int j = 0 ; j < 3 ; ++j){
        const int new_x = x/w + dx[i],
                  new_y = y/h + dy[j];

        const int chain = key(new_x, new_y);

        for(unsigned int i = 0 ; i < hsh[chain].size() ; ++i){
            const pair<int, int> now = hsh[chain][i];
            if(now.first <= x && x <= now.first + w && now.second <= y && y <= now.second + h)
                return 1;
        }
    }
    return 0;
}

void next_char(){
    ++at;
    if(at >= buff + sizeof(buff)){
        fread(buff, sizeof(buff), 1, stdin);
        at = buff;
    }
}

const int next_int(){
    int ret = 0;
    while(*at && (*at < '0' || *at > '9'))
        next_char();
    while(*at >= '0' && *at <= '9'){
        ret = ret * 10 + *at - '0';
        next_char();
    }
    return ret;
}

int main(){
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    fread(buff, sizeof(buff), 1, stdin);
    n = next_int();
    m = next_int();
    w = next_int();
    h = next_int();

    int x,y;
    for(int i = 0 ; i < n ; ++i){
        x = next_int();
        y = next_int();
        insert(x, y);
    }
    int fnd = 0;
    for(int i = 0 ; i < m ; ++i){
        x = next_int();
        y = next_int();
        if(search(x, y))
            ++fnd;
    }
    printf("%d\n", fnd);
}