Cod sursa(job #1091730)

Utilizator sebinechitasebi nechita sebinechita Data 25 ianuarie 2014 22:55:59
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("zc.in");
ofstream fout("zc.out");
#define MAX 1300100

pair<int, int> dx[MAX], dy[MAX];
int k, s;

void introdu(int a, int b)
{
    if(a<0 || b<0)
        return;
    if(!a && !b)
        return;
    ++k;
    dx[k].first=dy[k].second=a;
    dx[k].second=dy[k].first=b;
}

int findi(pair<int, int> a[], pair<int, int> b)
{
    return lower_bound(a+1, a+k+1, b)-a;
}

int main()
{
    int n, m, i, a, b, pozi, pozj, x;
    char c;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>a>>b;
        introdu(a, b);
        introdu(a-1, b);
        introdu(a-2, b);
        introdu(a-1, b-1);
        introdu(a-1, b+1);
        introdu(a+1, b);
        introdu(a+2, b);
        introdu(a+1, b-1);
        introdu(a+1, b+1);
        introdu(a, b-2);
        introdu(a, b-1);
        introdu(a, b+2);
        introdu(a, b+1);
    }
    sort(dx+1, dx+k+1);
    sort(dy+1, dy+k+1);
    n=k;
    k=0;
    for(i=1;i<=n;i++)
    {
        if(dx[i]!=dx[k])
        {
            dx[++k]=dx[i];
        }
    }
    k=0;
    for(i=1;i<=n;i++)
    {
        if(dy[i]!=dy[k])
        {
            dy[++k]=dy[i];
        }
    }
    pozi=0, pozj=0;
    while(m--)
    {
        fin>>c;
        fin>>x;
        if(c=='N')
        {
            s+=abs(findi(dx, make_pair(pozj,pozi+x ))-findi(dx, make_pair(pozj,pozi )));

            pozi+=x;
        }
        if(c=='S')
        {
            s+=abs(findi(dx, make_pair(pozj, pozi-x))-findi(dx, make_pair(pozj, pozi)));
            pozi-=x;
        }
        if(c=='E')
        {
            s+=abs(findi(dy, make_pair(pozi, pozj+x))-findi(dy, make_pair(pozi, pozj)));
            pozj+=x;
        }
        if(c=='V')
        {
            s+=abs(findi(dy, make_pair(pozi, pozj-x))-findi(dy, make_pair(pozi, pozj)));
            pozj-=x;
        }

    }
    fout<<s<<"\n";
}