Cod sursa(job #159320)

Utilizator stef2nStefan Istrate stef2n Data 14 martie 2008 01:35:48
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <vector>
using namespace std;

const int MAX_HASH = 666013;

int N, M, W, H;
vector < pair < pair <int, int>, pair <int, int> > > hash[MAX_HASH];

inline int h(const pair <int, int> &A)
{
    return (((long long) A.first << 20) + A.second) % MAX_HASH;
}

inline void insert_hash(const pair < pair <int, int>, pair <int, int> > &P)
{
    int key = h(P.first);
    hash[key].push_back(P);
}

bool find_hash(const pair <int, int> &pos, const pair <int, int> point)
{
    int key = h(pos);
    for(size_t i = 0; i < hash[key].size(); ++i)
        if(hash[key][i].first == pos)
            return hash[key][i].second.first <= point.first
                && hash[key][i].second.first + W >= point.first
                && hash[key][i].second.second <= point.second
                && hash[key][i].second.second + H >= point.second;
    return false;
}


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

    int x, y, cnt = 0, px, py;
    in >> N >> M >> W >> H;
    for(int i = 0; i < N; ++i)
    {
        in >> x >> y;
        insert_hash(make_pair(make_pair((2 * x - 1) / (2 * W), (2 * y - 1) / (2 * H)), make_pair(x, y)));
    }
    for(int i = 0; i < M; ++i)
    {
        in >> x >> y;
        px = (2 * x - 1) / (2 * W);
        py = (2 * y - 1) / (2 * H);
        cnt += find_hash(make_pair(px, py), make_pair(x, y))
            || (px > 0 && find_hash(make_pair(px - 1, py), make_pair(x, y)))
            || (py > 0 && find_hash(make_pair(px, py - 1), make_pair(x, y)))
            || (px > 0 && py > 0 && find_hash(make_pair(px - 1, py - 1), make_pair(x, y)));
    }

    out << cnt << endl;

    return 0;
}