Cod sursa(job #2342859)

Utilizator Iulia14iulia slanina Iulia14 Data 13 februarie 2019 14:12:33
Problema Zota & Chidil Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 6.44 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("zc.in");
ofstream cout ("zc.out");
struct ura{
    int x,y;
};
ura vc[1300005];
ura vl[1300005];
bool cmp1(ura a , ura b)
{
    if (a.x<b.x)
        return true;
    else
    if (a.x>b.x)
        return false;
    else
    {
        if (a.y<b.y)
            return true;
        return false;
    }
}
bool cmp2(ura a , ura b)
{
    if (a.y<b.y)
        return true;
    else
    if (a.y>b.y)
        return false;
    else
    {
        if (a.x<b.x)
            return true;
        return false;
    }
}
int main()
{
    int n,mm,st,dr,x,y,s=0,m,cnt=0,i,j,l,c,cnt1=0,cnt2=0,lf,cf,dir;
    char car;
    cin>>n>>mm;
    for (i=1;i<=n;i++)
    {
        cin>>c>>l;
        vc[++cnt].x=l-2;
        vc[cnt].y=c;
        vc[++cnt].x=l-1;
        vc[cnt].y=c-1;
        vc[++cnt].x=l-1;
        vc[cnt].y=c;
        vc[++cnt].x=l-1;
        vc[cnt].y=c+1;
        vc[++cnt].x=l;
        vc[cnt].y=c-2;
        vc[++cnt].x=l;
        vc[cnt].y=c-1;
        vc[++cnt].x=l;
        vc[cnt].y=c;
        vc[++cnt].x=l;
        vc[cnt].y=c+1;
        vc[++cnt].x=l;
        vc[cnt].y=c+2;
        vc[++cnt].x=l+1;
        vc[cnt].y=c-1;
        vc[++cnt].x=l+1;
        vc[cnt].y=c;
        vc[++cnt].x=l+1;
        vc[cnt].y=c+1;
        vc[++cnt].x=l+2;
        vc[cnt].y=c;
    }
    for (i=1;i<=cnt;i++)
    {
        vl[i].x=vc[i].x;
        vl[i].y=vc[i].y;
    }
    cnt1=cnt2=cnt;
    sort (vc+1,vc+cnt1+1,cmp2);
    sort (vl+1,vl+cnt2+1,cmp1);
 //   for (i=1;i<=cnt;i++)
   //     cout<<vl[i].x<<" "<<vl[i].y<<endl;
   // cout<<endl;
    //for (i=1;i<=cnt;i++)
    //    cout<<vc[i].x<<" "<<vc[i].y<<endl;
    l=0;
    c=0;
    lf=0;
    cf=0;
    for (i=1;i<=mm;i++)
    {
        cin>>car>>dir;
        lf=l;
        cf=c;
        x=y=0;
        if (car=='N')
        {
            lf+=dir;
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vc[m].y>c)
                    dr=m-1;
                else
                if (vc[m].y<c)
                    st=m+1;
                else
                {
                    if (vc[m].x<=l)
                        st=m+1;
                    else
                    {

                        x=m;
                        dr=m-1;
                    }
                }
            }
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vc[m].y>c)
                    dr=m-1;
                else
                if (vc[m].y<c)
                    st=m+1;
                else
                {
                    if (vc[m].x>lf)
                        dr=m-1;
                    else
                    {
                        y=m;
                        st=m+1;
                    }
                }
            }
        }
        if (car=='E')
        {
            cf+=dir;
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vl[m].x>l)
                    dr=m-1;
                else
                if (vl[m].x<l)
                    st=m+1;
                else
                {
                    if (vl[m].y<=c)
                        st=m+1;
                    else
                    {
                        x=m;
                        dr=m-1;
                    }
                }
            }
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vl[m].x>l)
                    dr=m-1;
                else
                if (vl[m].x<l)
                    st=m+1;
                else
                {
                    if (vl[m].y>cf)
                        dr=m-1;
                    else
                    {
                        y=m;
                        st=m+1;
                    }
                }
            }
        }
        if (car=='S')
        {
            lf-=dir;
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vc[m].y>c)
                    dr=m-1;
                else
                if (vc[m].y<c)
                    st=m+1;
                else
                {
                    if (vc[m].x<=lf)
                        st=m+1;
                    else
                    {
                        x=m;
                        dr=m-1;
                    }
                }
            }
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vc[m].y>c)
                    dr=m-1;
                else
                if (vc[m].y<c)
                    st=m+1;
                else
                {
                    if (vc[m].x>l)
                        dr=m-1;
                    else
                    {
                        y=m;
                        st=m+1;
                    }
                }
            }
        }
        if (car=='V')
        {
            cf-=dir;
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vl[m].x>l)
                    dr=m-1;
                else
                if (vl[m].x<l)
                    st=m+1;
                else
                {
                    if (vl[m].y<=cf)
                        st=m+1;
                    else
                    {
                        x=m;
                        dr=m-1;
                    }
                }
            }
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vc[m].x>l)
                    dr=m-1;
                else
                if (vc[m].x<l)
                    st=m+1;
                else
                {
                    if (vc[m].y>c)
                        dr=m-1;
                    else
                    {
                        y=m;
                        st=m+1;
                    }
                }
            }
        }
        l=lf;
        c=cf;
        if (x<=y&&x!=0&&y!=0)
        s+=(y-x+1);
    }
    cout<<s;
    return 0;
}