Cod sursa(job #498295)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 4 noiembrie 2010 19:43:15
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define maxim(a,b) (a>b ? a : b)
#define mp make_pair
#define CST 1300005
#define x first
#define y second
#define ll long long

ll 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};

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

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

int caut(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+1;
        else
        {
            ind1=mij;
            dr=mij-1;
        }
    }
    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 maxim(ind2-ind1+1,0);
}

int main ()
{
    int i,j,px,py,a,b,ind;
    char dir;
    ll l;
    
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d\n",&a,&b);
        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]!=mp(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++)
    {
        scanf("%c%lld\n",&dir,&l);
        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(qx,px,py+dy[ind],py+dy[ind]*l);
        else
            sol+=caut(qy,py,px+dx[ind],px+dx[ind]*l);
        px+=dx[ind]*l;
        py+=dy[ind]*l;
    }
    printf("%lld\n",sol);
    return 0;
}