Cod sursa(job #29680)

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

using namespace std;

#define MAX_N 50005
#define MAX_H 65536
#define SHIFT 16
#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, lg, Res; point P[MAX_N]; char buf[64];
unsigned short hash1[MAX_H][4], hash2[MAX_H][4];
char size1[MAX_H], size2[MAX_H]; 
unsigned odd1, odd2;

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, h1, h2; 

    x = (((x<<1)|1)/(W<<1)); 
    y = (((y<<1)|1)/(H<<1));
    t = (((x>>10)^(y&1023))<<10)|((x&1023)^(y>>10));
    h1 = (t * odd1) >> SHIFT;
    h2 = (t * odd2) >> SHIFT;
    if (size1[h1] < size2[h2])
        hash1[h1][size1[h1]++] = idx;
    else
        hash2[h2][size2[h2]++] = idx;
}

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); 
    W2 = W<<1; H2 = H<<1;
    srand(N^M^W^H);
    odd1 = (rand()<<1)|1; 
    odd2 = (rand()<<1)|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;
        x = (((x<<1)|1)/(W<<1));
        y = (((y<<1)|1)/(H<<1));
        t = (((x>>10)^(y&1023))<<10)|((x&1023)^(y>>10));
        for (p = hash1[(t * odd1) >> SHIFT]; *p; p++)
            if (included(P[0], P[*p])) 
            {
                Res++;
                break;
            }
        if (*p) continue;
        for (p = hash2[(t * odd2) >> SHIFT]; *p; p++)
            if (included(P[0], P[*p])) 
            {
                Res++;
                break;
            }
    }
    printf("%d\n", Res);

    return 0;
 }