Cod sursa(job #131830)

Utilizator vlad_popaVlad Popa vlad_popa Data 4 februarie 2008 15:27:21
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>

using namespace std;

#define NMAX 50001
#define mp make_pair
#define pb push_back

char sir[1<<6];
int N, M, W, H;
map < pair<int, int>, vector<int> > Hash;
int ogrx[NMAX], ogry[NMAX];

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[mp(ogrx[i] / W, ogry[i] / H)].pb(i);
    }
}

inline int Check_Hash (int a, int b, int x, int y)
{
    int i, sz, ii;
    for(i = 0, sz = Hash[mp(a, b)].size(); i < sz; ++ i)
    {
        ii = Hash[mp(a, b)][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;
}