Pagini recente » Cod sursa (job #1870798) | Cod sursa (job #136818) | Cod sursa (job #2524428) | Cod sursa (job #3193974) | Cod sursa (job #1886512)
#include <algorithm>
#include <fstream>
#include <string>
#define x first
#define y second
#define mp make_pair
using namespace std;
ifstream fin("zc.in");
ofstream fout("zc.out");
typedef long long i64;
typedef pair <int, int> str;
const int nmax= 100000;
const int afectat= 13;
int n, m, k;
str v1[nmax*afectat+1], v2[nmax*afectat+1], aux[nmax*afectat+1];
inline int av( int x ) {
if ( x<0 ) {
x= -x;
}
return x;
}
int f( str v[], str x ) {
if ( v[k]<=x ) {
return k;
}
int ans= 0;
for ( int i= k-1; ans<i; ) {
int aux= (ans+i)/2;
if ( v[aux+1]<=x ) {
ans= aux+1;
} else {
i= aux;
}
}
return ans;
}
string buffer;
string::iterator buffer_it;
void read_int( int &x ) {
for ( ; (*buffer_it>'9' || *buffer_it<'0') && *buffer_it!='-'; ++buffer_it ) ;
int sign= 1;
if ( *buffer_it=='-' ) {
sign= -1;
++buffer_it;
}
for ( x= 0; *buffer_it>='0' && *buffer_it<='9'; ++buffer_it ) {
x= x*10+*buffer_it-'0';
}
x*= sign;
}
void read_letter( char &x ) {
for ( ; *buffer_it<'A' || *buffer_it>'Z'; ++buffer_it ) ;
x= *buffer_it;
++buffer_it;
}
int main( ) {
getline( fin, buffer, (char)0 );
buffer_it= buffer.begin();
read_int(n), read_int(m);
for ( int i= 1, x, y; i<=n; ++i ) {
read_int(x), read_int(y);
for ( int a= x-2; a<=x+2; ++a ) {
for ( int b= y-2+av(x-a); b<=y+2-av(x-a); ++b ) {
if ( a!=0 || b!=0 ) {
aux[++k]= mp(a, b);
}
}
}
}
sort( aux+1, aux+k+1 );
int k2= 0;
for ( int i= 1; i<=k; ++i ) {
if ( aux[i].x!=v1[k2].x || aux[i].y!=v1[k2].y ) {
v1[++k2]= aux[i];
v2[k2].x= aux[i].y, v2[k2].y= aux[i].x;
}
}
k= k2;
sort( v2+1, v2+k+1 );
i64 sol= 0;
for ( int cnt= 1, x= 0, y= 0; cnt<=m; ++cnt ) {
char a;
int b;
read_letter(a), read_int(b);
if ( a=='N' ) {
sol= sol+f(v1, mp(x, y+b))-f(v1, mp(x, y));
y+= b;
} else if ( a=='S' ) {
sol= sol+f(v1, mp(x, y-1))-f(v1, mp(x, y-b-1));
y-= b;
} else if ( a=='E' ) {
sol= sol+f(v2, mp(y, x+b))-f(v2, mp(y, x));
x+= b;
} else {
sol= sol+f(v2, mp(y, x-1))-f(v2, mp(y, x-1-b));
x-= b;
}
}
fout<<sol<<"\n";
return 0;
}