Cod sursa(job #1206060)

Utilizator andreiiiiPopa Andrei andreiiii Data 8 iulie 2014 19:37:32
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

class FileInput {
    public:
        FileInput() {}
        FileInput(const char *filename) {
            file = fopen(filename, "r");
            fread(buffer, BUFFER_SIZE, 1, file);
            cursor = 0;
        }
        inline FileInput & operator >> (int &n) {
            while(buffer[cursor] == ' ' || buffer[cursor] == '\n') {
                advance();
            }
            n = 0;
            while(isdigit(buffer[cursor])) {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            return *this;
        }
    private:
        const static int BUFFER_SIZE = 1000000;
        FILE* file;
        char buffer[BUFFER_SIZE];
        int cursor;
        inline void advance() {
            ++ cursor;
            if(cursor == BUFFER_SIZE) {
                cursor = 0;
                fread(buffer, BUFFER_SIZE, 1, file);
            }
        }
} fin("ograzi.in");

class HashTable {
public:
    HashTable(const int _LX = 1, const int _LY = 1):
        LX(_LX),
        LY(_LY) {}

    int hashkey(const int pfirst, const int psecond) const
    {
        int x = pfirst % LX == 0 ? pfirst / LX - 1: pfirst / LX;
        int y = psecond % LY == 0 ? psecond / LY - 1: psecond / LY;
        return (x * 997 + y) % MOD;
    }

    void insert(const pair<int, int> add)
    {
        H[hashkey(add.first + LX, add.second + LY)].push_back(add);
    }

    int find(const pair<int, int> toFind, const int key) const
    {
        for (const auto p: H[key])
        {
            if (p.first <= toFind.first && toFind.first <= p.first + LX && p.second <= toFind.second && toFind.second <= p.second + LY)
                return 1;
        }

        return 0;
    }
private:
    static const int MOD = 666013;
    const int LX, LY;
    vector< pair<int, int> > H[MOD];
};

int main()
{
    freopen("ograzi.out", "w", stdout);

    int N, M, LX, LY;
    fin >> N >> M >> LX >> LY;

    HashTable H = HashTable(LX, LY);
    for (int i = 1; i <= N; i++)
    {
        int x, y;
        fin >> x >> y;

        H.insert(make_pair(x, y));
    }

    int Sol = 0;
    for (int i = 1; i <= M; i++)
    {
        pair<int, int> p;
        fin >> p.first >> p.second;

       if (H.find(p, H.hashkey(p.first, p.second)) || H.find(p, H.hashkey(p.first + LX, p.second)) || H.find(p, H.hashkey(p.first, p.second + LY)) || H.find(p, H.hashkey(p.first + LX, p.second + LY)))
            Sol++;
    }

    printf("%d\n", Sol);
}