Cod sursa(job #468334)

Utilizator DraStiKDragos Oprica DraStiK Data 3 iulie 2010 10:39:24
Problema Zota & Chidil Scor 20
Compilator cpp Status done
Runda Runda Pregatire ** Marime 2.78 kb
#include <algorithm>
#include <vector>
using namespace std;

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

int dx[LIM]={0,1,0,-1, 0,2,0,-2, 0,1,-1, 1,-1};
int dy[LIM]={0,0,1, 0,-1,0,2, 0,-2,1,-1,-1, 1};

vector <pair <int,int> > vx,vy;
int n,m,nrt;

void read ()
{
    int i,j,x,y;

    scanf ("%d%d",&n,&m);
    for (i=1; i<=n; ++i)
    {
        scanf ("%d%d",&x,&y);
        for (j=1; j<LIM; ++j)
        {
            vx.pb (mp (x+dx[j],y+dy[j]));
            vy.pb (mp (y+dy[j],x+dx[j]));
        }
    }
}

struct cmp
{
    bool operator () (const pair <int,int> &a,const pair <int,int> &b)
    {
        return a.fs<b.fs || (a.fs==b.fs && a.sc<b.sc);
    }
};

struct eql
{
    bool operator () (const pair <int,int> &a,const pair <int,int> &b)
    {
        return a.fs==b.fs && a.sc==b.sc;
    }
};

void solve ()
{
    vector <pair <int,int> > :: iterator it;
    int i,lg,st,dr,x,y;
    char tip[2];

    sort (vx.begin (), vx.end (),cmp ());
    sort (vy.begin (), vy.end (),cmp ());
    vx.resize (unique (vx.begin (),vx.end (),eql ())-vx.begin ());
    vy.resize (unique (vy.begin (),vy.end (),eql ())-vy.begin ());

    x=y=0;
    for (i=1; i<=m; ++i)
    {
        scanf ("%s%d",&tip,&lg);
        if (tip[0]=='N')
        {
            st=lower_bound (vx.begin (),vx.end (),mp (x,y+1),cmp ())-vx.begin ();
            dr=upper_bound (vx.begin (),vx.end (),mp (x,y+lg),cmp ())-vx.begin ();
            if (st<=dr && vx[st].fs==x && y<=vx[st].sc && vx[st].sc<=y+lg)
                nrt+=dr-st;
            y+=lg;
        }
        else if (tip[0]=='S')
        {
            st=lower_bound (vx.begin (),vx.end (),mp (x,y-lg),cmp ())-vx.begin ();
            dr=upper_bound (vx.begin (),vx.end (),mp (x,y-1),cmp ())-vx.begin ();
            if (st<=dr && vx[st].fs==x && y-lg<=vx[st].sc && vx[st].sc<=y)
                nrt+=dr-st;
            y-=lg;
        }
        else if (tip[0]=='E')
        {
            st=lower_bound (vy.begin (),vy.end (),mp (y,x+1),cmp ())-vy.begin ();
            dr=upper_bound (vy.begin (),vy.end (),mp (y,x+lg),cmp ())-vy.begin ();
            if (st<=dr && vy[st].fs==y && x<=vy[st].sc && vy[st].sc<=x+lg)
				nrt+=dr-st;
            x+=lg;
        }
        else if (tip[0]=='V')
        {
            st=lower_bound (vy.begin (),vy.end (),mp (y,x-lg),cmp ())-vy.begin ();
            dr=upper_bound (vy.begin (),vy.end (),mp (y,x-1),cmp ())-vy.begin ();
            if(st<=dr && vy[st].fs==y && x-lg<=vy[st].sc&& vy[st].sc<=x)
                nrt+=dr-st;
            x-=lg;
        }
    }
    printf ("%d",nrt);
}

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

    read ();
    solve ();

    return 0;
}