Pagini recente » Cod sursa (job #2935633) | Cod sursa (job #2246711) | Cod sursa (job #2014131) | Cod sursa (job #31317) | Cod sursa (job #595700)
Cod sursa(job #595700)
#include<stdio.h>
#include<algorithm>
using namespace std;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
struct punct {
int x,y;
};
punct poz[2000000];
int n,m,nr,dist,praf,nrr;
char c;
void ver(int i) {
if(i<0)
--nr;
}
bool cmp(punct a, punct b) {
if(a.x>b.x)
return 0;
if(a.x<b.x)
return 1;
if(a.y>b.y)
return 0;
return 1;
}
int main() {
int i,j,x,y,cx,cy,k,pas,dir;
punct p;
freopen("zc.in","r",stdin);
freopen("zc.out","w",stdout);
scanf("%d%d\n",&n,&m);
for(i=1;i<=n;++i) {
scanf("%d%d\n",&y,&x);
poz[++nr].x=x; poz[nr].y=y;
poz[++nr].x=x; poz[nr].y=y-1; ver(y-1);
poz[++nr].x=x; poz[nr].y=y-2; ver(y-2);
poz[++nr].x=x; poz[nr].y=y+1;
poz[++nr].x=x; poz[nr].y=y+2;
poz[++nr].x=x-2; poz[nr].y=y; ver(x-2);
poz[++nr].x=x+2; poz[nr].y=y;
poz[++nr].x=x-1; poz[nr].y=y;
poz[++nr].x=x-1; poz[nr].y=y-1;
if(x==1 || y==1)
--nr;
poz[++nr].x=x-1; poz[nr].y=y+1;
poz[++nr].x=x+1; poz[nr].y=y+1;
poz[++nr].x=x+1; poz[nr].y=y;
poz[++nr].x=x+1; poz[nr].y=y-1; ver(y-1);
}
sort(poz,poz+nr+1,cmp);
for(i=1;i<=nr;++i)
if(poz[i].x!=poz[i-1].x || poz[i].y!=poz[i-1].y)
poz[++nrr]=poz[i];
nr=nrr;
cx=0; cy=0;
p.x=cx; p.y=cy;
for(i=1;i<=m;++i) {
scanf("%c %d\n",&c,&dist);
if(c=='N')
dir=1;
if(c=='S')
dir=3;
if(c=='E')
dir=0;
if(c=='V')
dir=2;
for(j=1;j<=dist;++j) {
p.x+=dx[dir];
p.y+=dy[dir];
pas=1<<30;
for(k=0;pas!=0;pas>>=1) {
if(k+pas<=nr && cmp(poz[k+pas],p))
k+=pas;
}
if(p.x==poz[k].x && p.y==poz[k].y)
++praf;
}
}
printf("%d\n",praf);
return 0;
}