Cod sursa(job #843223)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 27 decembrie 2012 16:39:01
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <cstdio>
#include <cassert>
#include <vector>

#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;
const int MaxBuff = 1000000;
const int MaxValue = 1000001;
const int U = 666013;

int BuffI; char Buffer[MaxBuff];

inline int ReadX() {
    int X = 0;
    while (Buffer[BuffI] < '0' || Buffer[BuffI] > '9')
        if(++BuffI == MaxBuff)
            assert(fread(Buffer, 1, MaxBuff, stdin)), BuffI = 0;
    while(Buffer[BuffI] >= '0' && Buffer[BuffI] <= '9') {
        X = X * 10 + Buffer[BuffI] - '0';
        if(++BuffI == MaxBuff)
            assert(fread(Buffer, 1, MaxBuff, stdin)), BuffI = 0;
    }
    return X;
}

vector<Point> Hash[U];
int W, H;

inline int HashCode(const Point &P) {
    return (1LL * P.x * MaxValue + P.y) % U;
}

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) {
    int key = HashCode(Point(P.x / W, P.y / H));
    Hash[key].push_back(P);
}

inline bool CheckPoint(const Point &P) {
    for (int d = 0; d < 4; ++d) {
        Point GridP = Point(P.x / W + DX[d], P.y / H + DY[d]);
        if (GridP.x < 0 || GridP.y < 0)
            continue;
        int key = HashCode(GridP);
        for (size_t i = 0; i < Hash[key].size(); ++i)
            if (Inside(Hash[key][i], P))
                return true;
    }
    return false;
}

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