Cod sursa(job #1213362)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 27 iulie 2014 22:25:11
Problema Zota & Chidil Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
vector< pair <int,int> > 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;
}
inline int mod(int x)
{
    if(x<0)
        return -x;
    return x;
}
void Fill(int x,int y)
{
    for(int p=-2;p<=2;p++)
        for(int k=-2;k<=2;k++)
            if(mod(p)+mod(k)<=2 && (x+p!=0 || y+k!=0))
                Array.push_back(make_pair(x+p,y+k));
}
void Read()
{
    int i;
    scanf("%d",&N);
    scanf("%d",&M);
    for(i=1;i<=N;i++)
    {
        int x,y;
        scanf("%d%d\n" , &x , &y );
        Fill(y,x);
    }
    sort(Array.begin(),Array.end());
}
void Eliminate()
{
    int i,ind=0;
    int length=Array.size();
    Array.resize(unique(Array.begin(),Array.end())-Array.begin());
    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;
        scanf("%c %d\n" , &direction , &distance );
        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;
        }
    }
    printf("%d\n",Result);
}
int main()
{
    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);
    Read();
    Eliminate();
    simulateRoad();
    return 0;
}