Cod sursa(job #74857)

Utilizator sealTudose Vlad seal Data 28 iulie 2007 22:00:27
Problema Zota & Chidil Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
using namespace std;
#include<cstdio>
#include<list>
#include<vector>
#include<algorithm>
#define abs(a) ((a)<0?-(a):(a))
list< pair<int,int> > L;
vector< pair<int,int> > V1,V2;

bool cmp(pair<int,int> a, pair<int,int> b)
{
    if(a.second<b.second || a.second==b.second && a.first<b.first)
        return true;
    return false;
}

int main()
{
    char d;
    int n,m,x,y,i,j,ans=0;
    pair<int,int> p;
    vector< pair<int,int> >::iterator it1,it2;

    freopen("zc.in","r",stdin);
    scanf("%d%d",&n,&m);
    while(n--)
    {
        scanf("%d%d",&x,&y);
        for(i=x-2;i<=x+2;++i)
            for(j=y-2+abs(x-i);j<=y+2-abs(x-i);++j)
            {
                p.first=i;
                p.second=j;
                L.push_back(p);
            }
    }
    p.first=0;
    p.second=0;
    L.remove(p);
    L.sort();
    L.unique();
    V1.assign(L.begin(),L.end());
    V2.assign(L.begin(),L.end());
    sort(V2.begin(),V2.end(),cmp);
    
    scanf(" ");
    while(m--)
    {
        scanf("%c %d\n",&d,&i);
        if(d=='N')
        {
            it1=lower_bound(V1.begin(),V1.end(),p);
            p.second+=i;
            it2=lower_bound(V1.begin(),V1.end(),p);
        }
        if(d=='S')
        {
            it2=lower_bound(V1.begin(),V1.end(),p);
            p.second-=i;
            it1=lower_bound(V1.begin(),V1.end(),p);
        }
        if(d=='E')
        {
            it1=lower_bound(V2.begin(),V2.end(),p,cmp);
            p.first+=i;
            it2=lower_bound(V2.begin(),V2.end(),p,cmp);
        }
        if(d=='V')
        {
            it2=lower_bound(V2.begin(),V2.end(),p,cmp);
            p.first-=i;
            it1=lower_bound(V2.begin(),V2.end(),p,cmp);
        }
        ans+=it2-it1;
    }

    freopen("zc.out","w",stdout);
    printf("%d\n",ans);

    return 0;
}