Cod sursa(job #879043)

Utilizator deneoAdrian Craciun deneo Data 14 februarie 2013 21:52:43
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("ograzi.in");
ofstream fout("ograzi.out");

#define MOD 666013
#define BUF 10000

int N, M, W, H;
vector< pair<int, int> > HASH[MOD];

int get_key(int x, int y) {
    if (x < 0 || y < 0)
        return -1;
    return (1LL * x * 980123 + y) % MOD;
}

void parse(int &nr) {
    static int poz = 0; nr = 0;
    char c[BUF];

    if (poz == 0) {
        fin.getline(c, BUF, EOF);
        fin.clear();
    }


    while (c[poz] != ' ' && c[poz] != '\n' && c[poz] != '\0') {
        nr = (nr * 10) + c[poz] - '0';
        ++poz;
        if (poz == BUF - 1) {
            poz = 0;
            fin.getline(c, BUF, EOF);
            fin.clear();
        }
    }

    ++poz;
    if (poz == BUF - 1)
        poz = 0;
}

int main () {

    fin >> N >> M >> W >> H; fin.get();

    for (int i = 1; i <= N; ++i) {
        int x, y;
        parse(x); parse(y);
        HASH[get_key(x / W, y / H)].push_back(make_pair(x, y));
    }

    int rez = 0;

    for (int i = 1; i <= M; ++i) {
        int x, y;
        parse(x); parse(y);

        int ok = 0;

        for (int dx = -1; dx <= 0 && !ok; ++dx)
            for (int dy = -1; dy <= 0 && !ok; ++dy) {
                int key = get_key(x / W + dx, y / H + dy);
                if (key != -1)
                    for (int j = 0; j < HASH[key].size() && !ok; ++j) {
                        int cx = HASH[key][j].first;
                        int cy = HASH[key][j].second;
                        if (x >= cx && x <= cx + W)
                            if (y >= cy && y <= cy + H) {
                                ++rez;
                                ok = 1;
                            }
                    }
                }
     }

    fout << rez;

    return 0;
}