Cod sursa(job #974717)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 18 iulie 2013 00:37:03
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <utility>
#include <string.h>

using namespace std;

ifstream cin("ograzi.in");
ofstream cout("ograzi.out");


const int MOD = 123331;
const int oo = (1<<31)-1;
const int BUF = 100000;

vector<pair<int, int> > HASH[MOD];
char c[BUF];

void parse(int &nr) {
    static int poz = 0; nr = 0;

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

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

    ++poz;
    if (poz == BUF - 1)
        poz = 0;
}
int n, m, h, w;
inline int getkey(int x, int y){
    if(x<0 || y < 0)
        return -1;
    return (1LL * x * 980123 + y) % MOD;
}
int main()
{
    parse(n);
    parse(m);
    parse(w);
    parse(h);
    for(int i = 1 ; i <= n ; ++ i){
        int x, y;
        parse(x); parse(y);
        HASH[getkey(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 = getkey(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;
                            }
                    }
                }
    }
    cout << rez << "\n";
    cin.close();
    cout.close();
    return 0;
}