Cod sursa(job #1213328)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 27 iulie 2014 20:39:28
Problema Zota & Chidil Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("zc.in");
ofstream g("zc.out");
vector< pair <int,int> > X,Array,Array2;
int N,M,line,col,ind,Result;
const int limit=2000000000;
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)
            Array.push_back(make_pair(x+dx[i],y+dy[i]));
}
void Read()
{
    int i;
    f>>N>>M;
    for(i=1;i<=N;i++)
    {
        int x,y;
        f>>x>>y;
        Fill(y,x);
    }
    sort(Array.begin(),Array.end());
}
void Eliminate()
{
    int i;
    for(i=0;i<Array.size();i++)
    {
        if(Array[i]==Array[i+1])
        {
            Array.erase(Array.begin()+i,Array.begin()+i+1);
            --i;
        }
    }
    for(int i=0;i<Array.size();i++)
    {
        pair<int,int> X;
        X.first=Array[i].second;
        X.second=Array[i].first;
        Array2.push_back(X);
    }
    sort(Array2.begin(),Array2.end());
}
void simulateRoad()
{
    int i;
    for(i=1;i<=M;i++)
    {
        char direction;
        int distance;
        int x;
        f>>direction>>distance;
        x=distance;
        int aux1=0,aux2=0;
        pair <int,int> val,val2;
        val.first=line;
        val.second=col+1;
        switch(direction)
        {
            case 'S':val.first=col;val.second=line-1;val2.first=col;val2.second=line-x;low=lower_bound(Array2.begin(),Array2.end(),val2);up=upper_bound(Array2.begin(),Array2.end(),val); Result+=up-low; line-=distance;break;
            case 'N':val.first=col;val.second=line+1;val2.first=col;val2.second=line+x;low=lower_bound(Array2.begin(),Array2.end(),val);up=upper_bound(Array2.begin(),Array2.end(),val2); Result+=up-low;line+=distance;break;
            case 'E':val2.first=line;val2.second=col+x;low=lower_bound(Array.begin(),Array.end(),val);up=upper_bound(Array.begin(),Array.end(),val2); Result+=up-low;col+=distance;break;
            case 'V':val.second=col-1;val2.first=line;val2.second=col-x;low=lower_bound(Array.begin(),Array.end(),val2);up=upper_bound(Array.begin(),Array.end(),val); Result+=up-low;col-=distance;break;
        }
    }
    g<<Result<<"\n";
}
int main()
{
    Read();
    Eliminate();
    simulateRoad();
    return 0;
}