Cod sursa(job #1273543)

Utilizator gedicaAlpaca Gedit gedica Data 22 noiembrie 2014 17:20:44
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <algorithm>
#include <cstdio>
#define x first
#define y second

using namespace std;

const long long CST= 1300005;

long long sol;
int N, M, nr;
pair <int,int> qx[CST], qy[CST];
int dx[4]= {0,1,0,-1};
int dy[4]= {1,0,-1,0};

ifstream in( "zc.in" );
ofstream out( "zc.out" );

inline int modul(int val)
{
    if( val<0 ) return -val;
    return val;
}

void adaug( int px, int py )
{
    for( int i=-2; i<=2; ++i )
    {
        for( int  j=-2; j<=2; ++j )
        {
            if( modul(i)+modul(j)<=2 )
                qx[++nr]= make_pair(px+i,py+j);
        }
    }
}

int caut_binar( pair<int,int> v[], int f, int l1, int l2 )
{
    int st,dr,mij,aux,ind1=nr+1,ind2=0;

    if( l1>l2 )
        aux= l1,l1=l2,l2=aux;

    st=1;
    dr=nr;

    while( st<=dr )
    {
        mij= (st+dr)/2;
        if( v[mij].x<f || (v[mij].x==f && v[mij].y<l1) )
            st=++mij;
        else
        {
            ind1=mij;
            dr=--mij;
        }
    }
    st=1;
    dr=nr;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij].x>f || (v[mij].x==f && v[mij].y>l2))
            dr=mij-1;
        else
        {
            ind2=mij;
            st=mij+1;
        }
    }

    return max( ind2-ind1+1, 0 );
}

int main ()
{
    int px, py, a, b, ind;
    char dir;
    long long l;
    in >> N >> M;
    int i, j;

    for( i=1; i<=N; ++i )
    {
        in >> a >> b;
        in.get();
        adaug( a, b );
    }

    sort( qx+1, qx+nr+1 );

    for( i=2, j=1; i<=nr; ++i )
    {
        if( qx[i]!=qx[j] )
            qx[++j]=qx[i];
    }

    nr=j;
    for( i= 1,j= 0; i<=nr; ++i )
    {
        if( qx[i]!=make_pair(0,0) )
            qx[++j]=qx[i];
    }

    nr=j;
    for( i=1; i<=nr; ++i )
    {
        qy[i].x= qx[i].y;
        qy[i].y= qx[i].x;
    }

    sort( qy+1, qy+nr+1 );

    px= 0;
    py= 0;
    for( i= 1; i<=M; ++i )
    {
        in >> dir;
        in.get();
        in >> l;
        in.get();

        if(dir=='N')
            ind=0;
        else if(dir=='E')
            ind=1;
        else if(dir=='S')
            ind=2;
        else ind= 3;

        if( dir=='S' || dir=='N' )
            sol+= caut_binar( qx, px, py+dy[ind], py+dy[ind]*l );
        else
            sol+=caut_binar( qy, py, px+dx[ind], px+dx[ind]*l );

        px+= dx[ind]*l;
        py+= dy[ind]*l;
    }

    out << sol;
    return 0;
}