Cod sursa(job #578385)

Utilizator DraStiKDragos Oprica DraStiK Data 11 aprilie 2011 11:34:14
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 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 MAX 10005
#define BIT 10

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

char buff[MAX];
int poz=MAX-1;

inline void cit (int &x)
{
    for ( ; !('0'<=buff[poz] && buff[poz]<='9'); )
        if (++poz==MAX)
            fread (buff,1,MAX,stdin), poz=0;

    for (x=0; '0'<=buff[poz] && buff[poz]<='9'; )
    {
        x=x*10+buff[poz]-'0';
        if (++poz==MAX)
            fread (buff,1,MAX,stdin), poz=0;
    }
}

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

void read ()
{
    int i;

    cit (N); cit (M); cit (W); cit (H);
    for (i=1; i<=N; ++i)
    {
        cit (v[i].fs.fs); cit (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)
    {
        cit (pct.fs.fs); cit (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;
}