Cod sursa(job #2342891)

Utilizator Iulia14iulia slanina Iulia14 Data 13 februarie 2019 15:01:56
Problema Zota & Chidil Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 6.41 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,x1,x2,y1,y2,poz1,poz2,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].y;
        vl[i].y=vc[i].x;
        swap(vc[i].x,vc[i].y);
    }
    cnt1=cnt2=cnt;
    sort (vc+1,vc+cnt1+1,cmp2);
    sort (vl+1,vl+cnt2+1,cmp1);
    x1=0;
    y1=0;
    x2=0;
    y2=0;
    for (i=1;i<=mm;i++)
    {
        cin>>car>>dir;
        poz1=poz2=0;
        if (car=='N')
        {
            y2+=dir;
            st=1;
            dr=cnt;
            poz1=poz2=0;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vl[m].x>x1)
                    dr=m-1;
                else
                if (vl[m].x<x1)
                    st=m+1;
                else
                {
                    if (vl[m].y>y1)
                    {
                        poz1=m;
                        dr=m-1;
                    }
                    else
                        st=m+1;
                }
            }
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vl[m].x>x2)
                    dr=m-1;
                else
                if (vl[m].x<x2)
                    st=m+1;
                else
                {
                    if (vl[m].y<=y2)
                    {
                        poz2=m;
                        st=m+1;
                    }
                    else
                        dr=m-1;
                }
            }

        }
        else
        if (car=='S')
        {
            y2-=dir;
            st=1;
            dr=cnt;
            poz1=poz2=0;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vl[m].x>x2)
                    dr=m-1;
                else
                if (vl[m].x<x2)
                    st=m+1;
                else
                {
                    if (vl[m].y>=y2)
                    {
                        poz1=m;
                        dr=m-1;
                    }
                    else
                        st=m+1;
                }
            }
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vl[m].x>x1)
                    dr=m-1;
                else
                if (vl[m].x<x1)
                    st=m+1;
                else
                {
                    if (vl[m].y<y1)
                    {
                        poz2=m;
                        st=m+1;
                    }
                    else
                        dr=m-1;
                }
            }
        }
        else
        if (car=='E')
        {
            x2+=dir;
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vc[m].y>y1)
                    dr=m-1;
                else
                if (vc[m].y<y1)
                    st=m+1;
                else
                {
                    if (vc[m].x>x1)
                    {
                        poz1=m;
                        dr=m-1;
                    }
                    else
                        st=m+1;
                }
            }
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if(vc[m].y>y2)
                    dr=m-1;
                else
                if (vc[m].y<y2)
                    st=m+1;
                else
                {
                    if (vc[m].x<=x2)
                    {
                        poz2=m;
                        st=m+1;
                    }
                    else
                        dr=m-1;
                }
            }
        }
        else
        if (car=='V')
        {
            x2-=dir;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (vc[m].y>y2)
                    dr=m-1;
                else
                if (vc[m].y<y2)
                    st=m+1;
                else
                {
                    if (vc[m].x>=x2)
                    {
                        poz1=m;
                        dr=m-1;
                    }
                    else
                        st=m+1;
                }
            }
            st=1;
            dr=cnt;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if(vc[m].y>y1)
                    dr=m-1;
                else
                if (vc[m].y<y1)
                    st=m+1;
                else
                {
                    if (vc[m].x<x1)
                    {
                        poz2=m;
                        st=m+1;
                    }
                    else
                        dr=m-1;
                }
            }
        }
        if (poz1!=0&&poz2!=0)
        s=s+(poz2-poz1+1);
        x1=x2; y1=y2;
    }
    cout<<s;
    return 0;
}