Cod sursa(job #1663242)

Utilizator tudorv96Tudor Varan tudorv96 Data 25 martie 2016 18:17:16
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <vector>
using namespace std;

const int MOD = 10069;

vector <pair <int, int> > M[MOD];
int n, m, w, h, sol;

int f(int x, int y) {
    return (1000003LL * x + y) % MOD;
}

void add(int x, int y, int key) {
    for (vector <pair <int, int> > :: iterator it = M[key].begin(); it != M[key].end(); ++it)
        if (it -> first == x && it -> second == y)
            return;
    M[key].push_back(make_pair(x, y));
}

bool query(int x, int y, int key) {
    for (vector <pair <int, int> > :: iterator it = M[key].begin(); it != M[key].end(); ++it)
        if (x >= it ->first && x <= it -> first + w && y >= it -> second && y <= it -> second + h)
            return true;
    return false;
}

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

    fin >> n >> m >> w >> h;
    for (int x, y, i = 0; i < n; ++i) {
        fin >> x >> y;
        add(x, y, f(x / w, y / h));
    }
    for (int x, y, i = 0; i < m; ++i) {
        fin >> x >> y;
        const int dx[] = {0, 0, -1, -1};
        const int dy[] = {0, -1, 0, -1};
        for (int k = 0; k < 4; ++k) {
            if (query(x, y, f(x / w + dx[k], y / h + dy[k]))) {
                sol++;
                break;
            }
        }
    }

    fout << sol;

    fin.close();
    fout.close();
    return 0;

}