Pagini recente » Cod sursa (job #463228) | Cod sursa (job #2451015) | Cod sursa (job #656791) | Cod sursa (job #803729) | Cod sursa (job #66386)
Cod sursa(job #66386)
#include <cstdio>
#include <vector>
#include <algorithm>
#define fin "zc.in"
#define fout "zc.out"
using namespace std;
struct dot { int x,y; };
vector <dot> vx,vy;
int N,M;
long long ret;
bool cmpx(dot a,dot b) {
if (a.x < b.x)
return 1;
else
if (a.x == b.x && a.y < b.y)
return 1;
else
return 0;
}
bool cmpy(dot a,dot b) {
if (a.y < b.y)
return 1;
else
if (a.y == b.y && a.x < b.x)
return 1;
else
return 0;
}
int main() {
int i,j,x,y,x1,y1,len,li1=0,li2=0;
int m,lo,hi,st,dr;
dot tmp;
char dir;
freopen(fin,"r",stdin); freopen(fout,"w",stdout);
scanf("%d%d",&N,&M);
for (i=0;i<N;++i) {
scanf("%d%d",&x,&y);
for (j=x-2;j<=x+2;++j) {
tmp.x=j; tmp.y=y;
vx.push_back(tmp);
}
for (j=x-1;j<=x+1;++j) {
tmp.x=j; tmp.y=y-1;
vx.push_back(tmp);
tmp.y=y+1;
vx.push_back(tmp);
}
tmp.x=x; tmp.y=y+2;
vx.push_back(tmp);
tmp.x=x; tmp.y=y-2;
vx.push_back(tmp);
}
sort(vx.begin(),vx.end(),cmpx);
for (i=0;i<(int)vx.size();++i)
if (i==0 || !(vx[i].x==vx[i-1].x && vx[i].y==vx[i-1].y))
if (vx[i].x!=0 || vx[i].y!=0)
vy.push_back(vx[i]);
vx.clear();
for (i=0;i<(int)vy.size();++i)
vx.push_back(vy[i]);
sort(vy.begin(),vy.end(),cmpy);
sort(vx.begin(),vx.end(),cmpx);
x=0; y=0;
for (i=0;i<M;++i) {
fgetc(stdin);
scanf("%c%d",&dir,&len);
x1=x; y1=y;
if ((dir=='N' || dir=='S') && len) {
if (dir=='N') {
y1+=len;
++y;
li1=y; li2=y1;
}
if (dir=='S') {
y1-=len;
--y;
li1=y1; li2=y;
}
lo=0; hi=(int)vx.size()-1;
while (lo<=hi) {
m=(lo+hi)/2;
if ( vx[m].x < x1)
lo=m+1;
else
if ( vx[m].x == x1 )
if ( vx[m].y < li1 )
lo=m+1;
else
hi=m-1;
else
hi=m-1;
}
st=lo;
lo=st; hi=(int)vx.size()-1;
while (lo<=hi) {
m=(lo+hi)/2;
if ( vx[m].x > x1 )
hi=m-1;
else
if ( vx[m].x == x1 )
if (vx[m].y > li2)
hi=m-1;
else
lo=m+1;
else
lo=m+1;
}
dr=hi;
if (st<=dr)
ret+=(dr-st+1);
}
if ((dir=='E' || dir=='V') && len) {
if (dir=='E') {
x1+=len;
++x;
li1=x; li2=x1;
}
if (dir=='V') {
x1-=len;
--x;
li1=x1; li2=x;
}
lo=0; hi=(int)vy.size()-1;
while (lo<=hi) {
m=(lo+hi)/2;
if ( vy[m].y < y1)
lo=m+1;
else
if ( vy[m].y == y1 )
if ( vy[m].x < li1 )
lo=m+1;
else
hi=m-1;
else
hi=m-1;
}
st=lo;
lo=st; hi=(int)vy.size()-1;
while (lo<=hi) {
m=(lo+hi)/2;
if ( vy[m].y > y1 )
hi=m-1;
else
if ( vy[m].y == y1 )
if (vy[m].x > li2)
hi=m-1;
else
lo=m+1;
else
lo=m+1;
}
dr=hi;
if (st<=dr)
ret+=(dr-st+1);
}
x=x1; y=y1;
}
printf("%lld\n",ret);
return 0;
}