# include <stdio.h>
# include <stdlib.h>
typedef struct LISTA {long int *begin, *end;};
typedef struct PUNCT {long int x,y;};
typedef struct LISTE_COORD {long int coord, count; long int *begin;};
int compara_punct_x(const void *aa, const void *bb)
{
PUNCT *a=(PUNCT *)aa;
PUNCT *b=(PUNCT *)bb;
if (a->x > b->x) return 1;
if (a->x < b->x) return -1;
if (a->y > b->y) return 1;
return -1;
}
int compara_punct_y(const void *aa, const void *bb)
{
PUNCT *a=(PUNCT *)aa;
PUNCT *b=(PUNCT *)bb;
if (a->y > b->y) return 1;
if (a->y < b->y) return -1;
if (a->x > b->x) return 1;
return -1;
}
const long int vx[]={0,0,1,0,-1};
const long int vy[]={0,1,0,-1,0};
//////////
// VARIABILE GLOBALE
///////
# define MAXN 100000
long int sol=0;
long int n,m,linlen,collen;
LISTE_COORD lin[MAXN+1],col[MAXN+1];
long int *vallin,*valcol;
LISTA list[5];
long int deplasamente_list[]={-2,-1,0,-1,-2};
void citire_mine(FILE *f)
{
fscanf(f,"%ld%ld",&n,&m);
PUNCT *mina=(PUNCT *) malloc (sizeof(PUNCT)*(n+1));
long int i;
for (i=1;i<=n;i++)
fscanf(f,"%ld%ld",&mina[i].x,&mina[i].y);
vallin=(long int*) malloc (sizeof(long int)*(n+1));
qsort(mina+1,n,sizeof(PUNCT),compara_punct_x);
//ai punctele sortate in ordinea coordonatei x, acum pe fiecare
//coordonata iti trebuie un vector
for (i=1;i<=n;i++)
{
vallin[i]=mina[i].y;
if (i==1 || mina[i].x!=mina[i-1].x)
{
linlen++;
lin[linlen].coord=mina[i].x;
lin[linlen].count=1;
lin[linlen].begin=vallin+i;
}
else
lin[linlen].count++;
}
valcol=(long int*) malloc (sizeof(long int)*(n+1));
qsort(mina+1,n,sizeof(PUNCT),compara_punct_y);
mina[0].y=-2000000001;
//ai coordonatele sortatae in ordinea coordonatei y si repetam
for (i=1;i<=n;i++)
{
valcol[i]=mina[i].x;
if (i==1 || mina[i].y!=mina[i-1].y)
{
collen++;
col[collen].coord=mina[i].y;
col[collen].count=1;
col[collen].begin=valcol+i;
}
else
col[collen].count++;
}
free(mina);
}
void test_generare()
{
long int i,j;
for (i=1;i<=linlen;i++)
{
printf("Linia %ld: \n\t",lin[i].coord);
for (j=1;j<=lin[i].count;j++)
printf("%ld ",lin[i].begin[j-1]);
printf("\n");
}
getchar();
}
char index_dir(char dir)
{
if (dir=='N') return 1;
if (dir=='E') return 2;
if (dir=='S') return 3;
return 4;
}
void interschimba(long int &a, long int &b)
{
long int aux; aux=a;a=b;b=aux;
}
long int search_b(LISTE_COORD *liste, long int li, long int lf, long int key)
{
if (li>lf) return 0;
long int m=(li+lf)/2;
if (liste[m].coord==key) return m;
if (liste[m].coord>key) return search_b(liste,li,m-1,key);
return search_b(liste,m+1,lf,key);
}
void open_list(LISTA &l,long int coord_key,LISTE_COORD *liste,long int listelen, long int li, long int lf)
{
//trebuie mai intai sa cautam daca exista o lista cu coord_key
long int index=search_b(liste,1,listelen,coord_key);
if (index==0)
{
l.begin=NULL;
l.end=NULL;
}
else
{
//AICI SE POATE OPTIMIZA MASIV PRIN INCA 2 CAUTARI BINARE
l.begin=liste[index].begin;
l.end=liste[index].begin+liste[index].count-1;
}
}
void extract_list(long int &depl, long int &c_bomb, long int &listlen)
{
long int j,min=-1;
for (j=0;j<=2;j++)
{
if (list[j+2].begin && (min==-1 || (*list[j+2].begin)<(*list[min].begin) ) ) min=j+2;
if (j>0 && list[2-j].begin && (min==-1 || (*list[2-j].begin)<(*list[min].begin) ) ) min=2-j;
}
//tre' sa scoti din list
depl=min;
if (depl>2) depl%=2;
c_bomb=*list[min].begin;
if (list[min].begin==list[min].end)
{
list[min].begin=NULL;
listlen--;
}
else
{
list[min].begin++;
//printf("%ld==",*list[min].begin);
}
}
long int found (long int *v, long int val)
{
long int i,solloc=0,min;
for (i=0,min=0;i<=4;i++)
{
if (v[i]==val) solloc=1;
if (v[i]<v[min]) min=i;
}
if (v[min]<val) v[min]=val;
return solloc;
}
void print_liste()
{
printf("///\n/// Print Liste\n///\n");
long int j,*p;
for (j=0;j<=4;j++)
{
printf("%ld = ",j-2);
p=list[j].begin;
while (p && p<=list[j].end)
{
printf("%ld ",*p);
p++;
}
printf("\n");
}
printf("////\n");
}
long int calculeaza_patratele(long int xi, long int yi, long int xf, long int yf)
{
long int listslen=0,lastmod[5]={-1,-1,-1,-1,-1},li,lf,solloc=0,j,depl,c_bomb,c1;
//terbuie sa cautam listele corecte;
if (xi==xf)
{
c1=xi;
if (yf<yi) interschimba(yf,yi);
li=yi;lf=yf;
//x ramane constant
for (j=-2;j<=2;j++)
{
open_list(list[j+2],xi+j,lin,linlen,yi,yf);
if (list[j+2].begin!=NULL) listslen++;
}
}
else
{
c1=yi;
if (xf<xi) interschimba(xf,xi);
li=xi;lf=xf;
for (j=-2;j<=2;j++)
{
open_list(list[j+2],yi+j,col,collen,xi,xf);
if (list[j+2].begin!=NULL) listslen++;
}
}
//de aici calculam efectiv
//printf("Segment: %ld %ld %ld %ld\n",xi,yi, xf,yf);
//printf("Nr de liste : %ld\n",listslen);
while (listslen)
{
//incercam sa gasim pozitia din una din liste care are val-depl minima
extract_list(depl,c_bomb,listslen);
// print_liste();
//asta e coordonata minima, si care ajunge cel mai departe in spate
// printf("variatia: %ld coord_bombei: %ld\n",depl,c_bomb);
// getchar();
for (j=c_bomb-depl;j<=c_bomb+depl;j++)
if (j>=li && j<=lf && (j!=0 || c1 !=0) )
{
solloc+=1-found(lastmod,j);
printf("->%ld \n",solloc);
}
}
return solloc;
}
void calculeaza(FILE *f)
{
long int pas,x=0,y=0,xnou,ynou;unsigned long int d;char dir;
for (pas=1;pas<=m;pas++)
{
//citim din "f" o directie si o distanta
fscanf(f," %c %lu ", &dir, &d);
dir=index_dir(dir);
x+=vx[dir];
y+=vy[dir];
xnou=x+vx[dir]*(d-1);
ynou=y+vy[dir]*(d-1);
//printf("%ld %ld -> %ld %ld\n",x,y,xnou,ynou);
//getchar();
sol+=calculeaza_patratele(x,y,xnou,ynou);
//ATENTIE!!!
//aici, daca segmentul contine [0,0] si e bomba pe el ar trebui scoasa
x=xnou;
y=ynou;
}
}
int main()
{
FILE *f=fopen("zc.in","r");
citire_mine(f);
//test_generare();
calculeaza(f);
fclose(f);
FILE *g=fopen("zc.out","w");
fprintf(g,"%ld\n",sol);
fclose(g);
return 0;
}