Pagini recente » Cod sursa (job #1255472) | Cod sursa (job #1702248)
#include <bits/stdc++.h>
#define vmax 100001
#define ll long long
using namespace std;
ifstream fin("zc.in");
ofstream fout("zc.out");
struct punct
{
int x,y;
};
punct a[vmax*13];
int s[vmax*13];
int qx(punct a, punct b)
{
return a.x<b.x || (a.x==b.x && a.y<b.y);
}
int n,m,i,x,y,f;
char d;
ll sol,nr;
int caut(int x, int y)
{
int s=1,d=f,m,best;
while(s<=d)
{
m=s+(d-s)/2;
if(a[m].x<x)s=m+1,best=m;
else
if(a[m].x>x)d=m-1;
else
{
if(a[m].y<=y)
{
s=m+1;
best=m;
}
else
if(a[m].y>y)d=m-1;
}
}
return best;
}
int op(char d, ll nr)
{
int f1,f2,c=0;
if(d=='N')
{
f1=caut(x+nr,y);
f2=caut(x+1,y);
if(a[f2].x==a[f2-1].x && a[f2].y==a[f2-1].y)c=1;
return s[f1]-s[f2]+c;
}
if(d=='S')
{
f1=caut(x-nr,y);
f2=caut(x-1,y);
if(a[f2].x==a[f2-1].x && a[f2].y==a[f2-1].y)c=1;
return s[f1]-s[f2]+c;
}
if(d=='E')
{
f1=caut(x,y+nr);
f2=caut(x,y+1);
if(a[f2].x==a[f2-1].x && a[f2].y==a[f2-1].y)c=1;
return s[f1]-s[f2]+c;
}
if(d=='V')
{
f1=caut(x,y-nr);
f2=caut(x,y-1);
if(a[f2].x==a[f2-1].x && a[f2].y==a[f2-1].y)c=1;
return s[f1]-s[f2]+c;
}
}
int main()
{
fin>>n>>m;
for(i=1;i<=n;i++)
{
fin>>x>>y;
a[++f].x=x;
a[f].y=y;
a[++f].x=x-2;
a[f].y=y;
a[++f].x=x-1;
a[f].y=y-1;
a[++f].x=x-1;
a[f].y=y;
a[++f].x=x-1;
a[f].y=y+1;
a[++f].x=x;
a[f].y=y-2;
a[++f].x=x;
a[f].y=y-1;
a[++f].x=x;
a[f].y=y+1;
a[++f].x=x;
a[f].y=y+2;
a[++f].x=x+1;
a[f].y=y-1;
a[++f].x=x+1;
a[f].y=y;
a[++f].x=x+1;
a[f].y=y+1;
a[++f].x=x+2;
a[f].y=y;
}
sort(a+1,a+f+1,qx);
for(i=1;i<=f;i++)
s[i]=s[i-1]+(!(a[i].x==a[i-1].x && a[i].y==a[i-1].y));
while(m--)
{
fin>>d>>nr;
sol+=op(d,nr);
}
fout<<sol<<"\n";
return 0;
}