Pagini recente » Cod sursa (job #1479670) | Cod sursa (job #2853634) | Cod sursa (job #2001847) | Cod sursa (job #1526841) | Cod sursa (job #1403348)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define Nmax 100005
#define mod 666013
using namespace std;
int i,j,n,m,x,l,c,p,sol;
char ch;
vector < int >V[mod];
int ap(int x)
{
int i;
for (i=0;i<V[x%mod].size();i++)
if (V[x%mod][i]==x) return 1;
return 0;
}
struct nod
{
int x;
int y;
} v[Nmax],w[Nmax];
int cb1(int l)
{
int st=1,dr=n,mij=0;
while (st<=dr)
{
mij=(st+dr)/2;
if (v[mij].x>c && w[mij-1].x-c<-2) return mij;
if (v[mij].x-l<-2 && v[mij+1].x>l) return mij+1;
if (v[mij].x<l && v[mij].x-l>=-2 && v[mij-1].x-l<-2) return mij;
if (v[mij].x<l) st=mij+1;
else dr=mij-1;
}
return 0;
}
int cb2(int c)
{
int st=1,dr=n,mij=0;
while (st<=dr)
{
mij=(st+dr)/2;
if (w[mij].y>=c && w[mij-1].y-c<-2) return mij;
if (w[mij].y-c<-2 && w[mij+1].y>c) return mij+1;
if (w[mij].y<=c && w[mij].y-c>=-2 && w[mij-1].y-c<-2) return mij;
if (w[mij].y<c) st=mij+1;
else dr=mij-1;
}
return 0;
}
int cmp1(const nod a,const nod b)
{
if (a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int cmp2(const nod a,const nod b)
{
if (a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
int main()
{
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",&v[i].x,&v[i].y);
w[i]=v[i];
}
l=0; c=0;
sort(v+1,v+n+1,cmp1);
sort(w+1,w+n+1,cmp2);
for (i=1;i<=m;i++)
{
scanf("%c %d\n",&ch,&x);
if (ch=='N' || ch=='S')
{
if (i==3)
i=i;
p=cb1(l);
while (abs(v[p].x-l)<=2 && p<=n && p>0)
{
//if (abs(v[p].y-c)<=2)
{
if (abs(v[p].x-l)==0)
{
if (v[p].y<=c+x && v[p].y>=c && !ap(v[p].y))
{sol++; V[v[p].y%mod].push_back(v[p].y);}
if (v[p].y-1<=c+x && v[p].y-1>=c && !ap(v[p].y-1))
{sol++; V[(v[p].y-1)%mod].push_back(v[p].y-1);}
if (v[p].y+1<=c+x && v[p].y+1>=c && !ap(v[p].y+1))
{sol++; V[(v[p].y+1)%mod].push_back(v[p].y+1);}
if (v[p].y-2<=c+x && v[p].y-2>=c && !ap(v[p].y-2))
{sol++; V[(v[p].y-2)%mod].push_back(v[p].y-2);}
if (v[p].y+2<=c+x && v[p].y+2>=c && !ap(v[p].y+2))
{sol++; V[(v[p].y-2)%mod].push_back(v[p].y-2);}
}
if (abs(v[p].x-l)==1)
{
if (v[p].y<=c+x && v[p].y>=c && !ap(v[p].y))
{sol++; V[v[p].y%mod].push_back(v[p].y);}
if (v[p].y-1<=c+x && v[p].y-1>=c && !ap(v[p].y-1))
{sol++; V[(v[p].y-1)%mod].push_back(v[p].y-1);}
if (v[p].y+1<=c+x && v[p].y+1>=c && !ap(v[p].y+1))
{sol++; V[(v[p].y+1)%mod].push_back(v[p].y+1);}
}else
if (v[p].y<=c+x && v[p].y>=c && !ap(v[p].y))
{sol++; V[v[p].y%mod].push_back(v[p].y);}
}
p++;
}
if (ch=='N') c+=x;
else c-=x;
} else
{
p=cb2(c);
while (abs(v[p].y-c)<=2 && p<=n && p>0)
{
// if (abs(v[p].x-l)<=2)
{
if (abs(v[p].y-c)==0)
{
if (v[p].x<=l+x && v[p].x>=l && !ap(v[p].x))
{sol++; V[v[p].x%mod].push_back(v[p].x);}
if (v[p].x-1<=l+x && v[p].x-1>=l && !ap(v[p].x-1))
{sol++; V[(v[p].x-1)%mod].push_back(v[p].x-1);}
if (v[p].x+1<=l+x && v[p].x+1>=l && !ap(v[p].x+1))
{sol++; V[(v[p].x+1)%mod].push_back(v[p].x+1);}
if (v[p].x-2<=l+x && v[p].x-2>=l && !ap(v[p].x-2))
{sol++; V[(v[p].x-2)%mod].push_back(v[p].x-2);}
if (v[p].x+2<=l+x && v[p].x+2>=l && !ap(v[p].x+2))
{sol++; V[(v[p].x-2)%mod].push_back(v[p].x-2);}
}
if (abs(v[p].y-c)==1)
{
if (v[p].x<=l+x && v[p].x>=l && !ap(v[p].x))
{sol++; V[v[p].x%mod].push_back(v[p].x);}
if (v[p].x-1<=l+x && v[p].x-1>=l && !ap(v[p].x-1))
{sol++; V[(v[p].x-1)%mod].push_back(v[p].x-1);}
if (v[p].x+1<=l+x && v[p].x+1>=l && !ap(v[p].x+1))
{sol++; V[(v[p].x+1)%mod].push_back(v[p].x+1);}
}else
if (v[p].x<=l+x && v[p].x>=l && !ap(v[p].x))
{sol++; V[v[p].x%mod].push_back(v[p].x);}
}
p++;
}
if (ch=='E') l+=x;
else l-=x;
}
}
printf("%d",sol);
return 0;
}