Pagini recente » Cod sursa (job #203800) | Cod sursa (job #2791666) | Cod sursa (job #766614) | Cod sursa (job #1019949) | Cod sursa (job #1886495)
#include <algorithm>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("zc.in");
ofstream fout("zc.out");
typedef long long i64;
const int nmax= 100000;
const int afectat= 13;
int n, m, k;
struct str {
int x, y;
} v1[nmax*afectat+1], v2[nmax*afectat+1], aux[nmax*afectat+1];
inline str mp( int x, int y ) {
str sol;
sol.x= x, sol.y= y;
return sol;
}
inline int av( int x ) {
if ( x<0 ) {
x= -x;
}
return x;
}
bool cmp( str x, str y ) {
if ( x.x==y.x ) {
return x.y<y.y;
}
return x.x<y.x;
}
int f( str v[], str x ) {
if ( v[k].x<x.x || (v[k].x==x.x && v[k].y<=x.y) ) {
return k;
}
int ans= 0;
for ( int i= k-1; ans<i; ) {
int aux= (ans+i)/2;
if ( v[aux+1].x<x.x || (v[aux+1].x==x.x && v[aux+1].y<=x.y) ) {
ans= aux+1;
} else {
i= aux;
}
}
return ans;
}
int main( ) {
fin>>n>>m;
for ( int i= 1, x, y; i<=n; ++i ) {
fin>>x>>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, cmp );
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, cmp );
i64 sol= 0;
for ( int cnt= 1, x= 0, y= 0; cnt<=m; ++cnt ) {
string a;
int b;
fin>>a>>b;
if ( a[0]=='N' ) {
sol= sol+f(v1, mp(x, y+b))-f(v1, mp(x, y));
y+= b;
} else if ( a[0]=='S' ) {
sol= sol+f(v1, mp(x, y-1))-f(v1, mp(x, y-b-1));
y-= b;
} else if ( a[0]=='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;
}