Cod sursa(job #1741762)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 15 august 2016 00:29:04
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <iomanip>
#include <queue>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <set>
#include <map>
#include <stack>
using namespace std;

class InputReader {
    public:
        InputReader() {}
        InputReader(const char *file_name) {
            input_file = fopen(file_name, "r");
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >>(int &n) {
            while(buffer[cursor] < '0' || buffer[cursor] > '9') {
                advance();
            }
            n = 0;
            while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            return *this;
        }
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
            ++ cursor;
            if(cursor == SIZE) {
                cursor = 0;
                fread(buffer, SIZE, 1, input_file);
            }
        }
};
InputReader cin("ograzi.in");
ofstream cout("ograzi.out");

const int MOD = 30013;

int w, h;

int Hash(int x, int y) {
    return (x * 1000 + y) % MOD;
}

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

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

bool Find(pair<int, int> point) {
    for (int i = 0; i < 4; i++) {
        int which = Hash(point.first / w + dx[i], point.second / h + dy[i]);
        if (which < 0)
            continue;
        for (auto &value : table[which])
            if (value.first <= point.first && point.first <= value.first + w && value.second <= point.second && point.second <= value.second + h)
                return true;
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m >> w >> h;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        table[Hash(x / w, y / h)].push_back(make_pair(x, y));
    }
    int answer = 0;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        if (Find(make_pair(x, y)))
            answer++;
    }
    cout << answer;
    return 0;
}