Cod sursa(job #420468)

Utilizator edp100Edp100 edp100 Data 19 martie 2010 12:37:31
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.2 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

struct bum
{
    int x,y;
};

bum a1[100005],b1[100005];
int n,m,u,p1,p2,ps,st,dr,bombe;
int cp1,cp2,me,sc;

void adau(int a,int b)
{
    a1[++u].x=a;
    a1[u].y=b;
    b1[u].x=b;
    b1[u].y=a;
}

int cmp(bum a,bum b)
{
    if(a.x==b.x)
        return (a.y<b.y);
    return(a.x<b.x);
}

int main ()
{
    int cb,a,b,mut,i,nr1,nr2;
    char tip;
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);
    scanf("%d%d",&n,&me);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d\n",&b,&a);
        adau(a-2,b);    adau(a+2,b);
        adau(a-1,b);    adau(a-1,b-1);
        adau(a,b);      adau(a-1,b+1);
        adau(a+1,b);    adau(a+1,b-1);
        adau(a+1,b+1);  adau(a,b-2);
        adau(a,b+2);    adau(a,b+1);    adau(a,b-1);
    }
    sort(a1+1,a1+u+1,cmp); // dupa coloane
    sort(b1+1,b1+u+1,cmp); // dupa linie
    nr1=1;nr2=1;
    for(i=2;i<=u;i++)
    {
        if((a1[i].x != a1[i-1].x) || (a1[i].y != a1[i-1].y))
        {
            a1[++nr1].x=a1[i].x;
            a1[nr1].y=a1[i].y;
        }
        
        if((b1[i].x != b1[i-1].x) || (b1[i].y != b1[i-1].y))
        {
            b1[++nr2].x=b1[i].x;
            b1[nr1].y=b1[i].y;
        }

    }
    u=nr1;
    p1=0;p2=0;
    for(i=1;i<=me;i++)
    {
        scanf("%c%d\n",&tip,&mut);
        if(tip=='N')
        {
            ps=p1+mut;
            cb=1;
            sc=1;
        }
        if(tip=='S')
        {
            ps=p1-mut;
            cb=1;
            sc=1;mut*=-1;
        }
        if(tip=='E')
        {
            ps=p2+mut;
            cb=0;sc=2;
        }
        if(tip=='V')
        {
            ps=p2-mut;
            cb=0;sc=2;mut*=-1;
        }
        //////////////////////
        if(cb==1)
        {
            st=1;dr=u;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(b1[m].x<p2)
                    st=m+1;
                else
                    if(b1[m].x>p2)
                        dr=m-1;
                    else
                    {
                        if(b1[m].y<p1 && b1[m].y<ps)
                            st=m+1;
                        else
                            dr=m-1;
                    }
            }//while
            cp1=st;
            st=1;dr=u;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(b1[m].x<p2)
                    st=m+1;
                else
                    if(b1[m].x>p2)
                        dr=m-1;
                    else
                    {
                        if(b1[m].y>p1 && b1[m].y>ps)
                            dr=m-1;
                        else
                            st=m+1;
                    }
            }//while
            cp2=dr;
            if(cp2 && cp1)
                bombe+=cp2-cp1+1;
        }// if
        else
        {
            st=1;dr=u;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(a1[m].x<p1)
                    st=m+1;
                else
                    if(a1[m].x>p2)
                        dr=m-1;
                    else
                    {
                        if(a1[m].y<p2 && a1[m].y<ps)
                            st=m+1;
                        else
                            dr=m-1;
                    }
            }//while
            cp1=st;
            st=1;dr=u;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(a1[m].x<p1)
                    st=m+1;
                else
                    if(a1[m].x>p1)
                        dr=m-1;
                    else
                    {
                        if(a1[m].y>p2 && a1[m].y>ps)
                            dr=m-1;
                        else
                            st=m+1;
                    }
            }//while
            cp2=dr;
            if(cp2 && cp1 && cp2>=cp1)
                bombe+=cp2-cp1+1;

        }
        if(sc==1)
                p1+=mut;
            else
                p2+=mut;
    }   //for
    printf("%d\n",bombe);
    return 0;
}