Cod sursa(job #94487)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 23 octombrie 2007 12:46:06
Problema Ograzi Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#define NMAX 100010

struct dreptunghi
{
        int x1, y1, x2, y2;
} D[NMAX];

int N, M, Hash[(1<<22)+10], P=3866623, Q=4176691, W, H;

int t, m, p, ans, i, p10;
long long x, y;
double a, b, sq;


int init()
{
        srand(time(0));
        sq = sqrt(5);
        t = 15+rand()%12;
        m = ((1<<t)%P);
        p = 1+rand()%t;
        a = (sq-1)/2.0; b = (sq+1)/2.0;
}

int hash(int k, int l)
{
        x = (int)((m*a))%P; x = (x*k)%P;
        y = (int)((m*b))%Q; y = (y*l)%Q;
        x = (((x>>(t-p))%P)*(long long)Q)%P;
        y = (((y>>p)%Q)*(long long)P)%Q;
        ans = (x+y)%Q;
        return ans;
}

int include(int x, int y, int k)
{
        int x1 = D[k].x1, y1 = D[k].y1;
        int x2 = x1+W, y2 = y1, x3 = x1+W, y3 = y1+H, x4 = x1, y4 = y1+H;

        if ((x1<=x&&x<=x2)&&(y1<=y&&y<=y3)) return 1;
        else return 0;
}

int main()
{
        int i, x, y, nsol, d;

        freopen("ograzi.in", "r", stdin);
        scanf("%d%d%d%d", &N, &M, &W, &H);

        init();

        for (i = 1; i <= N; i++)
        {
                scanf("%d%d", &D[i].x1, &D[i].y1);
                D[i].x2 = D[i].x1+W; D[i].y2 = D[i].y1+H;
                x = D[i].x2; y = D[i].y2;
                Hash[ hash(x/W, y/H) ] = i;
        }

        for (i = nsol = 0; i < M; i++)
        {
                scanf("%d%d", &x, &y);
                d = Hash[ hash(x/W,y/H) ];
                nsol += include(x,y,d);
                d = Hash[ hash(1+(x/W),y/H) ];
                nsol += include(x,y,d);
                d = Hash[ hash(1+(x/W),1+(y/H)) ];
                nsol += include(x,y,d);
                d = Hash[ hash(x/W,1+(y/H)) ];
                nsol += include(x,y,d);
        }

        freopen("ograzi.out", "w", stdout);
        printf("%d\n", nsol);

        return 0;
        
}