Pagini recente » Cod sursa (job #2796006) | Cod sursa (job #1637234) | Cod sursa (job #831068) | Cod sursa (job #948802) | Cod sursa (job #1560308)
#include<cstdio>
#include<algorithm>
using namespace std;
struct eu{int x,y;};
eu v[100001];
struct eu2{int x1,y1,x2,y2,dir;};
eu2 vc[100001],vcc[1000001];
int xc,yc,i,j,n,m,dir,cate;
char c;
bool sorting(eu2 a,eu2 b)
{
if(a.dir<b.dir)
return 1;
if(a.dir>b.dir)
return 0;
if(a.dir==1&&(a.y1<b.y1||a.y1==b.y1&&a.x1<b.x1))
return 1;
if(a.dir==1||(a.x1>b.x1||a.x1==b.x1&&a.y1>b.y1))
return 0;
return 1;
}
int main ()
{
freopen("zc.in","r",stdin);
freopen("zc.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d%d",&v[i].x,&v[i].y);
cate++;
vcc[cate].dir=0;
vcc[cate].x1=v[i].x-2;
vcc[cate].x2=v[i].x-2;
vcc[cate].y1=v[i].y;
vcc[cate].y2=v[i].y;
cate++;
vcc[cate].dir=0;
vcc[cate].x1=v[i].x+2;
vcc[cate].x2=v[i].x+2;
vcc[cate].y1=v[i].y;
vcc[cate].y2=v[i].y;
cate++;
vcc[cate].dir=0;
vcc[cate].x1=v[i].x-1;
vcc[cate].x2=v[i].x-1;
vcc[cate].y1=v[i].y-1;
vcc[cate].y2=v[i].y+1;
cate++;
vcc[cate].dir=0;
vcc[cate].x1=v[i].x+1;
vcc[cate].x2=v[i].x+1;
vcc[cate].y1=v[i].y-1;
vcc[cate].y2=v[i].y+1;
cate++;
vcc[cate].dir=0;
vcc[cate].x1=v[i].x;
vcc[cate].x2=v[i].x;
vcc[cate].y1=v[i].y-2;
vcc[cate].y2=v[i].y+2;
cate++;
vcc[cate].dir=1;
vcc[cate].x1=v[i].x;
vcc[cate].x2=v[i].x;
vcc[cate].y1=v[i].y+2;
vcc[cate].y2=v[i].y+2;
cate++;
vcc[cate].dir=1;
vcc[cate].x1=v[i].x;
vcc[cate].x2=v[i].x;
vcc[cate].y1=v[i].y-2;
vcc[cate].y2=v[i].y-2;
cate++;
vcc[cate].dir=1;
vcc[cate].x1=v[i].x-1;
vcc[cate].x2=v[i].x+1;
vcc[cate].y1=v[i].y-1;
vcc[cate].y2=v[i].y-1;
cate++;
vcc[cate].dir=1;
vcc[cate].x1=v[i].x-1;
vcc[cate].x2=v[i].x+1;
vcc[cate].y1=v[i].y+1;
vcc[cate].y2=v[i].y+1;
cate++;
vcc[cate].dir=1;
vcc[cate].x1=v[i].x-2;
vcc[cate].x2=v[i].x+2;
vcc[cate].y1=v[i].y;
vcc[cate].y2=v[i].y;
}
for(i=1;i<=m;i++)
{
scanf("\n%c%d",&c,&dir);
if(c=='N')
{
vc[i].x1=xc;
vc[i].y1=yc+1;
vc[i].x2=xc;
vc[i].y2=yc+dir;
yc+=dir;
vc[i].dir=0;
}
if(c=='E')
{
vc[i].x1=xc+1;
vc[i].y1=yc;
vc[i].x2=xc+dir;
vc[i].y2=yc;
xc+=dir;
vc[i].dir=1;
}
if(c=='S')
{
vc[i].x1=xc;
vc[i].y1=yc-dir;
vc[i].x2=xc;
vc[i].y2=yc-1;
yc-=dir;
vc[i].dir=0;
}
if(c=='V')
{
vc[i].x1=xc-dir;
vc[i].y1=yc;
vc[i].x2=xc-1;
vc[i].y2=yc;
xc-=dir;
vc[i].dir=1;
}
}
sort(vc+1,vc+m+1,sorting);
sort(vcc+1,vcc+cate+1,sorting);
int sum=0;
for(i=1;i<=m;i++)
{
int l1,l2,mid,nr=0;
if(vc[i].dir==0)
{
l1=1;
l2=cate/2;
int o=0;
while(l1<=l2)
{
mid=(l1+l2)/2;
if(vcc[mid].x1==vc[i].x1)
{
o=mid;
l2=mid-1;
}
else
if(vcc[mid].x1>=vc[i].x1)
l2=mid-1;
else
l1=mid+1;
}
if(o!=0)
{
eu inter;
mid=o;
inter.x=-2000000001;
inter.y=-2000000002;
while(vcc[mid].x1==vc[i].x1)
{
if(vcc[mid].y1>=inter.y)
{
if(inter.x<=vc[i].y1)
inter.x=vc[i].y1;
if(inter.y>=vc[i].y2)
inter.y=vc[i].y2;
if(inter.y>=inter.x)
nr+=inter.y-inter.x+1;
inter.x=vcc[mid].y1;
inter.y=vcc[mid].y2;
}
else
if(vcc[mid].y2>=inter.y)
inter.y=vcc[mid].y1;
mid++;
}
if(inter.x<=vc[i].y1)
inter.x=vc[i].y1;
if(inter.y>=vc[i].y2)
inter.y=vc[i].y2;
if(inter.y>=inter.x)
nr+=inter.y-inter.x+1;
}
}
else
{
l1=cate/2+1;
l2=cate;
int o=0;
while(l1<=l2)
{
mid=(l1+l2)/2;
if(vcc[mid].y1==vc[i].y1)
{
o=mid;
l2=mid-1;
}
else
if(vcc[mid].y1>=vc[i].y1)
l2=mid-1;
else
l1=mid+1;
}
if(o!=0)
{
eu inter;
mid=o;
inter.x=-2000000001;
inter.y=-2000000002;
while(vcc[mid].y1==vc[i].y1)
{
if(vcc[mid].x1>=inter.y)
{
if(inter.x<=vc[i].x1)
inter.x=vc[i].x1;
if(inter.y>=vc[i].x2)
inter.y=vc[i].x2;
if(inter.y>=inter.x)
nr+=inter.y-inter.x+1;
inter.x=vcc[mid].x1;
inter.y=vcc[mid].x2;
}
else
if(vcc[mid].x2>=inter.y)
inter.y=vcc[mid].x1;
mid++;
}
if(inter.x<=vc[i].x1)
inter.x=vc[i].x1;
if(inter.y>=vc[i].x2)
inter.y=vc[i].x2;
if(inter.y>=inter.x)
nr+=inter.y-inter.x+1;
}
}
sum+=nr;
}
printf("%d",sum);
return 0;
}