Cod sursa(job #2841063)

Utilizator daria0123daria ghitescu daria0123 Data 29 ianuarie 2022 11:38:53
Problema Zota & Chidil Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <iostream>
#include <algorithm>

using namespace std;

struct punct
{
 int x, y;
};

int dx[13] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
int dy[13] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};
punct ox[1300005], oy[1300005];
int n, m, l=0;
long long ans = 0;
punct chidil;

bool cmp (punct a, punct b)
{
    return a.y<b.y || (a.y==b.y && a.x<b.x);
}

bool cmp2 (punct a, punct b)
{
    return !cmp(b, a);
}

int bs(punct *v, punct val)
{
    int st=1, dr=l, mid, last=0;
    while (st<=dr)
    {
        mid=(st+dr)/2;
        if(cmp2(v[mid], val))
        {
            last=mid;
            st=mid+1;
        }
        else dr=mid-1;
    }
    return last;
}
punct transform(punct x) {
    punct y;
    y.x = x.y;
    y.y = x.x;
    return y;
}
int main()
{
    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        int x, y;
        cin>>y>>x;
        for(int j=0; j<13; j++)
        {
            l++;
            ox[l].x = x+dx[j];
            ox[l].y=y+dy[j];

            oy[l].y = x+dx[j];
            oy[l].x=y+dy[j];

        }
    }

    sort ( ox+1, ox+1+l, cmp);
    sort ( oy+1, oy+1+l , cmp);

    for(int i=1; i<=m; i++)
    {
        punct dest;
        char dir;
        int dist;
        cin>>dir>>dist;

        if(dir=='S')
        {
            dest=chidil;
            dest.x-=dist;
            ans+= bs(ox, chidil)-bs(ox, dest);
        }
        else if (dir=='N')
        {
            dest=chidil;
            dest.x+=dist;
            ans += bs(ox, dest) - bs(ox, chidil);

        }
        else if(dir=='V')
        {
            dest=chidil;
            dest.y-=dist;
            ans+=bs(oy, transform(chidil))-bs(oy, transform(dest));
        }
        else
        {
            dest=chidil;
            dest.y+=dist;
            ans+=bs(oy, transform(dest))-bs(oy, transform(chidil));
        }
        chidil = dest;

    }
    cout<<ans;
    return 0;
}