Cod sursa(job #131831)

Utilizator vlad_popaVlad Popa vlad_popa Data 4 februarie 2008 15:30:58
Problema Ograzi Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define NMAX 50001
#define pb push_back
#define PRIM 666013
#define H1 13
#define H2 113

char sir[1<<6];
int N, M, W, H;
vector <int> Hsh[PRIM];
int ogrx[NMAX], ogry[NMAX];

inline void Hash (int a, int b, int x)
{
    Hsh[(a*H1 + b*H2) % PRIM].pb(x);
}

void read ()
{
    int i, j, l, ten;
    scanf ("%d %d %d %d\n", &N, &M, &W, &H);
    
    for (i = 1; i <= N; ++ i)
    {
        gets (sir);
        for (ten = 1, l = strlen(sir) - 1; sir[l] != ' '; -- l, ten *= 10)
            ogry[i] += (sir[l] - '0') * ten;
        for (ten = 1, -- l; l >= 0; -- l, ten *= 10)
            ogrx[i] += (sir[l] - '0') * ten;
            
        Hash (ogrx[i] / W, ogry[i] / H, i);
    }
}

inline int Check_Hash (int a, int b, int x, int y)
{
    int i, sz, ii;
    for(i = 0, sz = Hsh[(a*H1 + b*H2) % PRIM].size(); i < sz; ++ i)
    {
        ii = Hsh[(a*H1 + b*H2) % PRIM][i];
        if (ogrx[ii] <= x && ogrx[ii] + W >= x)
            if (ogry[ii] <= y && ogry[ii] + H >= y)
                return 0;
    }
    return 1;
}

void solve ()
{
    int i, j, l, ten, x, y;
    int Ans = 0;
    
    for (i = 1; i <= M; ++ i)
    {
        x = y = 0;
        gets (sir);
        for (ten = 1, l = strlen(sir) - 1; sir[l] != ' '; -- l, ten *= 10)
            y += (sir[l] - '0') * ten;
        for (ten = 1, -- l; l >= 0; -- l, ten *= 10)
            x += (sir[l] - '0') * ten;
            
        Ans += !(Check_Hash(x/W, y/H, x, y) * Check_Hash(x/W-1, y/H, x, y) * Check_Hash(x/W, y/H-1, x, y) * Check_Hash(x/W-1, y/H-1, x, y));
    }
    
    printf ("%d\n", Ans);
}

int
 main ()
{
    freopen ("ograzi.in", "rt", stdin);
    freopen ("ograzi.out", "wt", stdout);
    
    read ();
    solve ();
    
    return 0;
}