Cod sursa(job #842535)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 26 decembrie 2012 23:46:18
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <cassert>
#include <vector>
#include <map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> Point;

const int DX[] = {0, 1, 0, 1}, DY[] = {0, 0, 1, 1};
const int MaxN = 50005;

map< Point, vector<Point> > Hash;
int W, H;

inline bool Inside(const Point R, const Point P) {
    return (R.x <= P.x && P.x <= R.x + W && R.y <= P.y && P.y <= R.y + H);
}

inline void Insert(const Point P) {
    for (int d = 0; d < 4; ++d) {
        Point GridP = Point(P.x / W + DX[d], P.y / H + DY[d]);
        if (Hash.find(GridP) == Hash.end())
            Hash[GridP] = vector<Point>();
        Hash[GridP].push_back(P);
    }
}

inline bool CheckPoint(const Point P) {
    Point GridP = Point(P.x / W, P.y / H);
    if (Hash.find(GridP) == Hash.end())
        return false;
    for (size_t i = 0; i < Hash[GridP].size(); ++i)
        if (Inside(Hash[GridP][i], P))
            return true;
    return false;
}

int main() {
    assert(freopen("ograzi.in", "r", stdin));
    assert(freopen("ograzi.out", "w", stdout));
    int N, M; assert(scanf("%d %d %d %d", &N, &M, &W, &H)== 4);
    for (; N > 0; --N) {
        Point P; assert(scanf("%d %d", &P.x, &P.y) == 2);
        Insert(P);
    }
    int Solution = 0;
    for (; M > 0; --M) {
        Point P; assert(scanf("%d %d", &P.x, &P.y) == 2);
        Solution += CheckPoint(P);
    }
    printf("%d\n", Solution);
    return 0;
}