Cod sursa(job #1213397)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 27 iulie 2014 23:40:23
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
ifstream f("zc.in");
ofstream g("zc.out");
vector< pair <int,int> > Array,Array2;
int N,M,line,col,ind,Result;
const int limit=2000000000;
char Str[5000005];
char Dir[100005];
int Dist[100005];
pair<int,int> A,B;
vector< pair <int,int> > :: iterator low,up;
int dx[]={-1,-1,-1,0,0,0,0,0,1,1,1,-2,2};
int dy[]={1,0,-1,-2,-1,0,1,2,-1,0,1,0,0};
inline bool Valid(int x,int y)
{
    return x>=-limit && y>=-limit && x<=limit && y<=limit;
}

void Fill(int x,int y)
{
    for(int i=0;i<13;i++)
        if(Valid(x+dx[i],y+dy[i])==1 && (x+dx[i]!=0 || y+dy[i]!=0))
            Array.push_back(make_pair(x+dx[i],y+dy[i]));
}
inline bool isCh(char ch)
{
    return ch>='A' && ch<='Z';
}
inline bool isDig(char ch)
{
    return ch>='0' && ch<='9';
}
void Read()
{
    int i;
    f>>N>>M;
    char ch;
    f.get(ch);
    int j=0;
    f.get(Str,5000005,EOF);
    for(i=1;i<=N;i++)
    {
        int x=0,y=0,value=0;
        bool after=0;
        int sign=1;
        while(Str[j]!='\n')
        {
            if(Str[j]==' ')
            {
                x*=sign,after=1,sign=1;
                ++j;
                continue;
            }
            if(Str[j]=='-')
                sign=-1;
            else
            {
                if(after==1)
                    y=y*10+Str[j]-'0';
                else
                    x=x*10+Str[j]-'0';
            }
            ++j;
        }
        y*=sign;
        ++j;
        Fill(y,x);
    }
    for(int i=1;i<=M;i++)
    {
        while(Str[j]!='\n' && Str[j]!=0)
        {
            if(isCh(Str[j])==1)
                Dir[i]=Str[j];
            if(isDig(Str[j]))
                Dist[i]=Dist[i]*10+Str[j]-'0';
            ++j;
        }
        ++j;
    }
    sort(Array.begin(),Array.end());
}
void Eliminate()
{
    int i,ind=0;
    int length=Array.size();
    for(i=1;i<Array.size();i++)
    {
        if(Array[i]!=Array[i+1])
            Array[++ind]=Array[i];
    }
    Array.resize(ind+1);
    for(int i=0;i<Array.size();i++)
        Array2.push_back(make_pair(Array[i].second,Array[i].first));
    sort(Array2.begin(),Array2.end());
}
void simulateRoad()
{
    int i;
    for(i=1;i<=M;i++)
    {
        char direction;
        int distance;
        int x;
        direction=Dir[i];
        distance=Dist[i];
        x=distance;
        switch(direction)
        {
            case 'S':Result+=upper_bound(Array2.begin(),Array2.end(),make_pair(col,line-1))-lower_bound(Array2.begin(),Array2.end(),make_pair(col,line-x)); line-=distance;break;
            case 'N':Result+=upper_bound(Array2.begin(),Array2.end(),make_pair(col,line+x))-lower_bound(Array2.begin(),Array2.end(),make_pair(col,line+1));line+=distance;break;
            case 'E':Result+=upper_bound(Array.begin(),Array.end(),make_pair(line,col+x))-lower_bound(Array.begin(),Array.end(),make_pair(line,col+1));col+=distance;break;
            case 'V':Result+=upper_bound(Array.begin(),Array.end(),make_pair(line,col-1))-lower_bound(Array.begin(),Array.end(),make_pair(line,col-x));col-=distance;break;
        }
    }
    g<<Result<<"\n";
}
int main()
{
    Read();
    Eliminate();
    simulateRoad();
    return 0;
}