Pagini recente » Cod sursa (job #377643) | Cod sursa (job #1825966) | Cod sursa (job #2924319) | Cod sursa (job #1048746) | Cod sursa (job #68964)
Cod sursa(job #68964)
#include<stdio.h>
typedef struct
{
long x,y;
} coord;
coord a;
coord vx[1000000],vy[1000000];
long n, m, nr;
void bubley(coord x[])
{
long i, j, ok=1;
coord aux;
while (ok)
{
ok=0;
for (i=1; i<nr; i++)
if (x[i].y>x[i+1].y || (x[i].y==x[i+1].y && x[i].x>x[i+1].x))
{
aux=x[i];
x[i]=x[i+1];
x[i+1]=aux;
ok=1;
}
}
}
void bublex(coord x[])
{
long i, j, ok=1;
coord aux;
while (ok)
{
ok=0;
for (i=1; i<nr; i++)
if (x[i].x>x[i+1].x || (x[i].x==x[i+1].x && x[i].y>x[i+1].y))
{
aux=x[i];
x[i]=x[i+1];
x[i+1]=aux;
ok=1;
}
}
}
int cautarex(coord x)
{
long i, j, m;
i=1; j=nr;
m=(i+j)/2;
while (i<=j)
{
if (vx[m].x==x.x && vx[m].y==x.y) return 1;
else if (vx[m].x==x.x) if(vx[m].y>x.y) {j=m-1; m=(i+j)/2;}
else {i=m+1; m=(i+j)/2;}
else if (vx[m].x>x.x) {j=m-1; m=(i+j)/2;}
else {i=m+1; m=(i+j)/2;}
}
return 0;
}
int cautarey(coord x)
{
long i, j, m;
i=1; j=nr;
m=(i+j)/2;
while (i<=j)
{
if (vy[m].x==x.x && vy[m].y==x.y) return 1;
else if (vy[m].y==x.y) if(vy[m].x>x.x) {j=m-1; m=(i+j)/2;}
else {i=m+1; m=(i+j)/2;}
else if (vy[m].y>x.y) {j=m-1; m=(i+j)/2;}
else {i=m+1; m=(i+j)/2;}
}
return 0;
}
int main()
{
freopen("zc.in","r",stdin);
freopen("zc.out","w",stdout);
scanf("%ld %ld",&n,&m);
long i, j, d;
for (i=1; i<=n; i++)
{
nr++;
scanf("%ld %ld",&vx[nr].x,&vx[nr].y);
if (vx[nr].x!=0 || vx[nr].y!=0) {
vy[nr].x=vx[nr].x;
vy[nr].y=vx[nr].y;} else nr--;
d=nr;
if (vx[nr].x-2!=0 || vx[nr].y!=0){
nr++;
vx[nr].x=vy[nr].x=vx[d].x-2;
vy[nr].y=vx[nr].y=vx[d].y;}
if (vx[nr].x-1!=0 || vx[nr].y!=0){
nr++;
vx[nr].x=vy[nr].x=vx[d].x-1;
vy[nr].y=vx[nr].y=vx[d].y;}
if (vx[nr].x+1!=0 || vx[nr].y!=0){
nr++;
vx[nr].x=vy[nr].x=vx[d].x+1;
vy[nr].y=vx[nr].y=vx[d].y;}
if (vx[nr].x+2!=0 || vx[nr].y!=0){
nr++;
vx[nr].x=vy[nr].x=vx[d].x+2;
vy[nr].y=vx[nr].y=vx[d].y;}
if (vx[nr].x!=0 || vx[nr].y-2!=0){
nr++;
vx[nr].x=vy[nr].x=vx[d].x;
vy[nr].y=vx[nr].y=vx[d].y-2;}
if (vx[nr].x!=0 || vx[nr].y-1!=0){
nr++;
vx[nr].x=vy[nr].x=vx[d].x;
vy[nr].y=vx[nr].y=vx[d].y-1;}
if (vx[nr].x!=0 || vx[nr].y+1!=0){
nr++;
vx[nr].x=vy[nr].x=vx[d].x;
vy[nr].y=vx[nr].y=vx[d].y+1;}
if (vx[nr].x!=0 || vx[nr].y+2!=0){
nr++;
vx[nr].x=vy[nr].x=vx[d].x;
vy[nr].y=vx[nr].y=vx[d].y+2;}
}
bublex(vx);
bubley(vy);
a.x=a.y=0;
long contor=0;
for (i=1; i<=m; i++)
{
char c;
long l, x;
scanf("%c",&c);
while (c=='\n') {scanf("%c",&c);}
scanf("%ld",&l);
switch (c)
{
case 'N' :{x=a.y+l;while (a.y<=x)
{ a.y++; if (cautarey(a) && cautarex(a)) contor++;}
break;
}
case 'S' :{x=a.y-l;while (a.y>x)
{ a.y--; if (cautarey(a) && cautarex(a)) contor++;}
break;
}
case 'E' :{x=a.x+l;while (a.x<x)
{ a.x++; if (cautarey(a) && cautarex(a)) contor++;}
break;
}
case 'V' :{x=a.x-l;while (a.x>x)
{ a.x--; if (cautarey(a) && cautarex(a)) contor++;}
break;
}
}
}
printf("%ld",contor);
return 0;
}