Cod sursa(job #29664)

Utilizator dominoMircea Pasoi domino Data 9 martie 2007 19:06:49
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 50005
#define MAX_H 32768
#define SHIFT 17
#define FIN "ograzi.in"
#define FOUT "ograzi.out"
#define x first
#define y second

typedef pair<int, int> point;

int N, M, W, H, W2, H2, Res; point P[MAX_N]; char buf[64];
unsigned short hash[MAX_H][16]; char size[MAX_H]; unsigned odd;

inline point get(void)
{
    int a, b; char *p;

    fgets(buf, sizeof(buf), stdin);
    for (p = buf, a = 0; *p >= '0' && *p <= '9'; p++)
        a = a*10+ *p-'0';
    for (; *p == ' '; p++);
    for (b = 0; *p >= '0' && *p <= '9'; p++)
        b = b*10 + *p-'0';
    return make_pair(a, b);
}

inline void insert(int x, int y, int idx)
{
    unsigned t, hval; 

    t = (((x<<1)|1)/(W<<1)) ^ (((y<<1)|1)/(H<<1));
    hval = (t * odd) >> SHIFT;
    hash[hval][size[hval]++] = idx;
    while (size[hval] > 16);
}

inline int included(point p, point q)
{
    return q.x <= p.x && p.x <= q.x+W && q.y <= p.y && p.y <= q.y+H;
}

int main(void)
{
    int i, x, y, t;
    unsigned short *p;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d %d %d %d\n", &N, &M, &W, &H); 
    srand(N+M+W+H);
    odd = (rand()<<1)|1; 
    W2 = W<<1; H2 = H<<1;
    for (i = 1; i <= N; i++)
    {
        P[i] = get();
        insert(P[i].x, P[i].y, i);
        insert(P[i].x+W, P[i].y, i);
        insert(P[i].x, P[i].y+H, i);
        insert(P[i].x+W, P[i].y+H, i);
    }
    for (i = 1; i <= M; i++)
    {
        P[0] = get();
        x = P[0].first; y = P[0].second;
        t = (((x<<1)|1)/(W<<1)) ^ (((y<<1)|1)/(H<<1));
        for (p = hash[(t * odd) >> SHIFT]; *p; p++)
            if (included(P[0], P[*p])) 
            {
                Res++;
                break;
            }
    }
    printf("%d\n", Res);

    return 0;
}