Cod sursa(job #2025797)

Utilizator lflorin29Florin Laiu lflorin29 Data 23 septembrie 2017 11:50:24
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;

#define ll long long
int n, m, w, h, sol;

const int MOD = 666013;
const int P = 1e9 + 7;
pair <int, int>have[MOD];
int cod(int x, int y) {
    return (1LL * x * P + y) % MOD;
}
void addHash(int x, int y) {
    have[cod(x / w, y / h)] = {x, y};
}

bool inside(int a, int b, int c, int d, int x, int y) {
    return x >= a && x <= c && y >= b && y <= d;
}

inline bool inHash(ll codN) {
    return have[codN].first != -1;
}
int main() {
    ifstream cin("ograzi.in");
    ofstream cout("ograzi.out");
    cin >> n >> m >> w >> h;
    for(int i = 0; i < MOD; ++i) have[i] = make_pair(-1, -1);
    for(int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        addHash(x, y);
    }

    for(int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        int cx = x / w, cy = y / h;
        vector <pair<int, int> > check;
        check.emplace_back(cx, cy), check.emplace_back(cx - 1, cy);
        check.emplace_back(cx, cy - 1), check.emplace_back(cx - 1, cy - 1);

        for(auto it : check) {
            ll itcod = cod(it.first, it.second);

            if(inHash (itcod)) {
                int chkx = have[itcod].first, chky = have[itcod].second;

                if(inside(chkx, chky, chkx + w, chky + h, x, y)) {
                    ++sol;
                    break;
                }
            }
        }
    }

    cout << sol;
    return 0;
}