Cod sursa(job #13826)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 7 februarie 2007 16:24:07
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxx 130010
#define maxd 13
#define ll long long 

int n,m,l,k;
int dirx[maxd]={-2,-1,-1,-1,0,0,0,0,0,1,1,1,2};
int diry[maxd]={0,-1,0,1,-2,-1,0,1,2,-1,0,1,0};
int a[maxx],b[maxx],c[maxx],d[maxx],p[maxx],q[maxx];
ll sol;

int cmp(int x,int y)
{
    return ((a[x]<a[y]) || ((a[x]==a[y]) && (b[x]<b[y])));
}

int cmp2(int x,int y)
{
    return ((d[x]<d[y]) || ((d[x]==d[y]) && (c[x]<c[y])));
}

void elimin(int a[],int b[],int p[])
{
     k=0;
     int i,j,x,y,x2,y2;
     
     for (i=1;i<=l;)
     {
         for (j=i+1;i<=l && a[p[j]]==a[p[j+1]] && b[p[j]]==b[p[j+1]];j++);
         k++;
         a[p[k]]=a[p[i]];
         b[p[k]]=b[p[i]];         
         i=j;
     }
}

int search(int a[],int b[],int p[],int x,int y)
{
    int front=1,middle,back=l,aux=l+1;
    
	while (front<=back)
	{
		  middle=(front+back)/2;

		  if ((a[p[middle]]>x) || ((a[p[middle]]==x) && (b[p[middle]]>y)))
		  {
			   aux=middle;
			   back=middle-1;
		  }
		  else front=middle+1;
	}
	
    return aux;
}

int main()
{
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);
    
    scanf("%d %d ",&n,&m);
    
    int i,j,cx,cy,dx,x,y,x2,y2;
    char dir;
    
    for (i=1;i<=n;++i)
    {
        scanf("%d %d ",&x,&y);
        for (j=0;j<maxd;++j)
        {
            cx=x+dirx[j];
            cy=y+diry[j];
            if ((cx!=0) || (cy!=0))
            {
                ++l;
                a[l]=cx;
                b[l]=cy;
                c[l]=cx;
                d[l]=cy;
                p[l]=l;
                q[l]=l;
            }
        }
    }
    
	sort(p+1,p+l+1,cmp);
	sort(q+1,q+l+1,cmp2);

    elimin(a,b,p);
    elimin(c,d,q);
    l=k;
    x=0;
    y=0;
    
    for (i=1;i<=m;i++)
    {
        scanf("%c %d ",&dir,&dx);
        
        if (dir=='N')
        {
            x2=x;
            y2=y+dx;
			sol+=search(a,b,p,x2,y2)-search(a,b,p,x,y);
        }
        
        if (dir=='V')
        {
            x2=x-dx;
            y2=y; 
            sol+=search(d,c,q,y,x-1)-search(d,c,q,y2,x2-1);
        }
        
        if (dir=='S')
        {
            x2=x;
            y2=y-dx;
            sol+=search(a,b,p,x,y-1)-search(a,b,p,x2,y2-1);
        }
        
        if (dir=='E')
        {
            x2=x+dx;
            y2=y;
            sol+=search(d,c,q,y2,x2)-search(d,c,q,y,x);
        }
        
        x=x2;
        y=y2;
    }
    
    printf("%lld\n",sol);
    
    return 0;
}