Cod sursa(job #1761438)

Utilizator silkMarin Dragos silk Data 22 septembrie 2016 11:07:40
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.26 kb
#include <cstdio>
#include <algorithm>
#define NMax 1400000
using namespace std;

struct zc{ int x,y; };
zc x0[NMax+1];
zc y0[NMax+1];
zc tx[NMax+1];
zc ty[NMax+1];

int dirx[12]={0,1,0,-1,1,1,-1,-1,0,2,0,-2};
int diry[12]={1,0,-1,0,1,-1,1,-1,2,0,-2,0};
int N,M,xi,yi,x,y,o;
long long ans;

bool cmp1(const zc A, const zc B)
{
    if(A.x==B.x)
    return A.y<B.y;
return A.x<B.x;
}

bool cmp2(const zc A, const zc B)
{
    if(A.y==B.y)
    return A.x<B.x;
return A.y<B.y;
}

void swap(int& A, int& B)
{
    int aux;
    aux = A;
    A = B;
    B = aux;
}

int Search_yi_x0()
{
    int st,dr,mid,f1=0;
    for(st = 1, dr = o; st <= dr; )
    {
    mid = (st+dr)/2;
    if( x0[mid].x > x ) dr = mid-1;
    else if( x0[mid].x < x ) st = mid+1;
    else{
            if( x0[mid].y < yi ) st = mid+1; else if( x0[mid].y > y ) dr = mid-1; else { f1 = mid; dr = mid-1; }
        }
    }
    return f1;
}

int Search_yf_x0()
{
    int st,dr,mid,f2=0;
    for(st = 1, dr = o; st <= dr; ){
    mid = (st+dr)/2;
    if( x0[mid].x > x ) dr = mid-1;
    else if( x0[mid].x < x ) st = mid+1;
    else
        {
            if( x0[mid].y < yi ) st = mid+1; else if( x0[mid].y > y ) dr = mid-1; else { f2 = mid; st = mid+1; }
        }
    }
    return f2;
}

int Search_xi_y0()
{
    int st,dr,mid,f1=0;
    for(st = 1, dr = o; st <= dr; ){
        mid = (st+dr)/2;
        if( y0[mid].y > y ) dr = mid-1;
        else if( y0[mid].y < y ) st = mid+1;
        else
        {
            if( y0[mid].x < xi ) st = mid+1; else if( y0[mid].x > x ) dr = mid-1; else { f1 = mid; dr = mid-1; }
        }
    }
    return f1;
}

int Search_xf_y0()
{
    int st,dr,mid,f2=0;
    for(st = 1, dr = o; st <= dr; ){
        mid = (st+dr)/2;
        if( y0[mid].y > y ) dr = mid-1;
        else if( y0[mid].y < y ) st = mid+1;
        else
        {
            if( y0[mid].x < xi ) st = mid+1; else if( y0[mid].x > x ) dr = mid-1; else { f2 = mid; st = mid+1; }
        }
    }
    return f2;
}

void SolveN(int q)
{
    int f1=0,f2=0;

    f1 = Search_yi_x0();
    f2 = Search_yf_x0();
    if(f1 && f2) ans = ans + (f2-f1+1);
    if(f2 && x0[f2].y==y && q < M) --ans;
}

void SolveS(int q)
{
    int f1=0,f2=0;

    swap(xi,x);
    swap(yi,y);

    f1 = Search_yi_x0();
    f2 = Search_yf_x0();
    if(f1 && f2) ans = ans + (f2-f1+1);
    if(f2 && x0[f1].y==yi && q < M) --ans;

    swap(xi,x);
    swap(yi,y);
}

void SolveE(int q)
{
    int f1=0,f2=0;

    f1 = Search_xi_y0();
    f2 = Search_xf_y0();

    if(f1 && f2) ans = ans + (f2-f1+1);
    if(f2 && y0[f2].x==x && q < M) --ans;
}

void SolveV(int q)
{
    int f1=0,f2=0;

    swap(xi,x);
    swap(yi,y);

    f1 = Search_xi_y0();
    f2 = Search_xf_y0();
    if(f1 && f2) ans = ans + (f2-f1+1);
    if(f1 && y0[f1].x==xi && q < M) --ans;

    swap(xi,x);
    swap(yi,y);
}

int main(){
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);

    int i,j,k,nc,v;
    char ch;

    scanf("%d %d\n",&N,&M);
    for(nc = 0, i = 1; i <= N; ++i)
    {
        ++nc;
        scanf("%d %d\n",&x,&y);
        tx[nc].x = ty[nc].x = x;
        tx[nc].y = ty[nc].y = y;

        for(k = 0; k < 12; ++k)
        if( ( x+dirx[k] ) || ( y+diry[k] ) )
        {
            ++nc;
            tx[nc].x = ty[nc].x = x + dirx[k];
            tx[nc].y = ty[nc].y = y + diry[k];
        }
    }

    sort(tx+1,tx+nc+1,cmp1);
    sort(ty+1,ty+nc+1,cmp2);

    for(o = 0, i = 1; i <= nc; )
    {
        for(j = i; tx[i].x==tx[j].x && tx[i].y==tx[j].y && j <= nc; ++j);
        x0[++o] = tx[i];
        i = j;
    }

    for(o = 0, i = 1; i <= nc; )
    {
        for(j = i; ty[i].x==ty[j].x && ty[i].y==ty[j].y && j <= nc; ++j);
        y0[++o] = ty[i];
        i = j;
    }

    x = y = 0;
    for(i = 1; i <= M; ++i)
    {
        scanf("%c %d\n",&ch,&v);
        if(ch=='N') ch = 0;
        else if(ch=='E') ch = 1;
        else if(ch=='S') ch = 2;
        else ch = 3;

        xi = x; yi = y;
        x = x + dirx[ch]*v;
        y = y + diry[ch]*v;

        if(ch==0) SolveN(i);
        else if(ch==1) SolveE(i);
        else if(ch==2) SolveS(i);
        else SolveV(i);
    }

    printf("%lld\n",ans);



return 0;
}