Pagini recente » Cod sursa (job #1182302) | Cod sursa (job #1449569) | Cod sursa (job #2267568) | Cod sursa (job #259549) | Cod sursa (job #1724375)
#include <cstdio>
#include <algorithm>
#define MAXN 100000
#define MAXDIST 2
FILE*fi,*fout;
class Point{
public :
int x;
int y;
};
Point Vx[13*MAXN+1],Vy[13*MAXN+1],vx[13*MAXN+1],vy[13*MAXN+1];
char dublux[13*MAXN+1],dubluy[13*MAXN+1];
bool cmp1(Point a,Point b){
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
bool cmp2(Point a,Point b){
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
#define MAXBUF (1<<20)
char buf[MAXBUF];
int pos=MAXBUF;
inline char nextch(){
if(pos==MAXBUF){
fread(buf,1,MAXBUF,fi);
pos=0;
}
return buf[pos++];
}
inline int getnr(){
char a=nextch();
if(a=='N'||a=='S'||a=='V'||a=='E')
return a;
else{
int semn=1;
if(a=='-')
semn=-1;
while(a<'0'||a>'9')
a=nextch();
int nr=0;
while(a>='0'&&a<='9'){
nr=nr*10+a-'0';
a=nextch();
}
return nr*semn;
}
}
inline int myabs(int x){
if(x<0)
x=-x;
return x;
}
int main(){
int i,j,n,m,ix,iy,l,conx,cony,rez1,rez2,pas,x,y,x1,y1,x2,y2,x11,y11,x22,y22;
long long con;
char dir;
fi=fopen("zc.in" ,"r");
fout=fopen("zc.out" ,"w");
n=getnr();
m=getnr();
con=0;
for(i=1; i<=n; i++){
x=getnr();
y=getnr();
for(ix=-2;ix<=2;ix++)
for(iy=-2;iy<=2;iy++)
if(myabs(ix)+myabs(iy)<=MAXDIST){
con++;
Vx[con].x=x+ix;
Vx[con].y=y+iy;
Vy[con].x=Vx[con].x;
Vy[con].y=Vx[con].y;
}
}
std::sort(Vx+1,Vx+con+1,cmp1);
std::sort(Vy+1,Vy+con+1,cmp2);
i=1;
while(i<=13*n){
j=i+1;
while(j<=13*n&&Vx[i].x==Vx[j].x&&Vx[i].y==Vx[j].y){
dublux[j]=1;
j++;
}
i=j;
}
conx=0;
for(i=1;i<=13*n;i++)
if(dublux[i]==0){
conx++;
vx[conx]=Vx[i];
}
i=1;
while(i<=13*n){
j=i+1;
while(j<=13*n&&Vy[i].x==Vy[j].x&&Vy[i].y==Vy[j].y){
dubluy[j]=1;
j++;
}
i=j;
}
cony=0;
for(i=1;i<=13*n;i++)
if(dubluy[i]==0){
cony++;
vy[cony]=Vy[i];
}
x1=y1=0;
x2=y2=0;
con=0;
for(i=1;i<=m;i++){
dir=getnr();
l=getnr();
if(dir=='N'){
y2+=l;
y1++;
}
if(dir=='S'){
y2-=l;
y1--;
}
if(dir=='E'){
x2+=l;
x1++;
}
if(dir=='V'){
x2-=l;
x1--;
}
if(dir=='N'||dir=='S'){
if(y1>y2){
y11=y2;
y22=y1;
}
else{
y11=y1;
y22=y2;
}
rez1=0;
for(pas=1<<16;pas;pas>>=1)
if(rez1+pas<=conx&&(vx[rez1+pas].x<x1||(vx[rez1+pas].x==x1&&vx[rez1+pas].y<y11)))
rez1+=pas;
rez2=0;
for(pas=1<<16;pas;pas>>=1)
if(rez2+pas<=conx&&(vx[rez2+pas].x<x1||(vx[rez2+pas].x==x1&&vx[rez2+pas].y<=y22)))
rez2+=pas;
con=con+rez2-rez1;
}
else{
if(x1>x2){
x11=x2;
x22=x1;
}
else{
x11=x1;
x22=x2;
}
rez1=0;
for(pas=1<<16;pas;pas>>=1)
if(rez1+pas<=cony&&(vy[rez1+pas].y<y1||(vy[rez1+pas].y==y1&&vy[rez1+pas].x<x11)))
rez1+=pas;
rez2=0;
for(pas=1<<16;pas;pas>>=1)
if(rez2+pas<=cony&&(vy[rez2+pas].y<y1||(vy[rez2+pas].y==y1&&vy[rez2+pas].x<=x22)))
rez2+=pas;
con=con+rez2-rez1;
}
x1=x2;
y1=y2;
}
fprintf(fout,"%lld" ,con);
fclose(fi);
fclose(fout);
return 0;
}