Cod sursa(job #1172898)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 18 aprilie 2014 11:27:22
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <vector>
#include <cstring>

#define vint vector<point>::iterator
#define mod 666013

using namespace std;

ifstream fin ("ograzi.in");
ofstream fout ("ograzi.out");

struct point
{
    int x,y;
};
int n,m,w,h,hh,x,xx,y,yy,p,len,nr;
vector<point> H[mod];

char s[3000000];

int get_int ()
{
    int x = 0;

    for (; p < len; ++p)
    {
        if ('0' <= s[p] && s[p] <= '9')
        {
            x = x*10 + s[p] - '0';
        }
        else
        {
            ++p;
            break;
        }
    }

    return x;
}

bool test (int x, int y, int hh)
{
    for (vint it = H[hh].begin (); it != H[hh].end(); ++it)
    {
        if (it->x <= x && x <= it->x + w && it->y <= y && y <= it->y + h)
            return 1;
    }
    return 0;
}

int main()
{
    freopen ("ograzi.in","r",stdin);

    fread (s,1,3000000,stdin);
    len = strlen(s);
    p = 0;

    n = get_int ();
    m = get_int ();
    w = get_int ();
    h = get_int ();

    for (int i=1; i<=n; ++i)
    {
        x = get_int ();
        y = get_int ();

        if (x/w*w == x)
            xx = x;
        else xx = (x/w + 1)*w;

        if (y/h*h == y)
            yy = y;
        else yy = (y/h + 1)*h;

        hh =(xx*23+yy*31)%mod;
        point P; P.x = x; P.y = y;
        H[hh].push_back (P);
    }

    for (int i=1; i<=m; ++i)
    {
        x = get_int ();
        y = get_int ();

        if (x/w*w == x)
            xx = x - w;
        else xx = x/w*w;

        if (y/h*h == y)
            yy = y - h;
        else yy = y/h*h;

        if (test (x,y,(xx*23+yy*31)%mod))
        {
            ++nr;
            continue;
        }

        xx += w;

        if (test (x,y,(xx*23+yy*31)%mod))
        {
            ++nr;
            continue;
        }

        yy += h;

        if (test(x,y,(xx*23+yy*31)%mod))
        {
            ++nr;
            continue;
        }

        xx -= w;

        if (test(x,y,(xx*23+yy*31)%mod))
        {
            ++nr;
        }
    }

    fout<<nr;
}