Cod sursa(job #578380)

Utilizator DraStiKDragos Oprica DraStiK Data 11 aprilie 2011 11:32:01
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define sc second
#define fs first

#define MOD 666013
#define DIM 50005
#define BIT 10

pair <pair <int,int>,pair <int,int> > v[DIM];
vector <int> h[MOD];
int N,M,W,H,cnt;

inline int code (pair <int,int> x)
{
    return ((x.fs<<10)+x.sc)%MOD;
}

void read ()
{
    int i;

    scanf ("%d%d%d%d",&N,&M,&W,&H);
    for (i=1; i<=N; ++i)
    {
        scanf ("%d%d",&v[i].fs.fs,&v[i].fs.sc);
        v[i].sc.fs=(int)(((double)v[i].fs.fs+W-0.5)/W);
        v[i].sc.sc=(int)(((double)v[i].fs.sc+H-0.5)/H);
        h[code (v[i].sc)].pb (i);
    }
}

inline int is_inside (pair <int,int> drpt,pair <int,int> x)
{
    return drpt.fs<=x.fs && drpt.sc<=x.sc && x.fs<=drpt.fs+W && x.sc<=drpt.sc+H;
}

inline int find (pair <pair <int,int>,pair <int,int> > x,int dx,int dy)
{
    vector <int> :: iterator it;

    x.sc.fs+=dx;
    x.sc.sc+=dy;

    for (it=h[code (x.sc)].begin (); it!=h[code (x.sc)].end (); ++it)
        if (v[*it].sc==x.sc)
        {
            if (is_inside (v[*it].fs,x.fs))
                return 1;

            return 0;
        }

    return 0;
}

void solve ()
{
    pair <pair <int,int>,pair <int,int> > pct;
    int i;

    for (i=1; i<=M; ++i)
    {
        scanf ("%d%d",&pct.fs.fs,&pct.fs.sc);
        pct.sc.fs=(int)(((double)pct.fs.fs-0.5)/W);
        pct.sc.sc=(int)(((double)pct.fs.sc-0.5)/H);

        if (find (pct,0,0) || find (pct,1,0) || find (pct,0,1) || find (pct,1,1))
            ++cnt;
    }

    printf ("%d",cnt);
}

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

    read ();
    solve ();

    return 0;
}