Cod sursa(job #94491)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 23 octombrie 2007 13:09:36
Problema Ograzi Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.84 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=(1<<21)-1, Q=(1<<22)-1, W, H;

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


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

int hash(int k, int l)
{
        long long f;
        x = (a*k)&P; y = (b*l)&Q;
        f = (x*y)&P;
        ans = ((x>>(t-p))+(y>>p)+(f>>t))&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+H;

        if ((x1<=x&&x<=x2)&&(y1<=y&&y<=y2)) 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;
        
}