Pagini recente » Cod sursa (job #2831264) | Cod sursa (job #693018) | Cod sursa (job #201642) | Cod sursa (job #541689) | Cod sursa (job #1273543)
#include <fstream>
#include <algorithm>
#include <cstdio>
#define x first
#define y second
using namespace std;
const long long CST= 1300005;
long long sol;
int N, M, nr;
pair <int,int> qx[CST], qy[CST];
int dx[4]= {0,1,0,-1};
int dy[4]= {1,0,-1,0};
ifstream in( "zc.in" );
ofstream out( "zc.out" );
inline int modul(int val)
{
if( val<0 ) return -val;
return val;
}
void adaug( int px, int py )
{
for( int i=-2; i<=2; ++i )
{
for( int j=-2; j<=2; ++j )
{
if( modul(i)+modul(j)<=2 )
qx[++nr]= make_pair(px+i,py+j);
}
}
}
int caut_binar( pair<int,int> v[], int f, int l1, int l2 )
{
int st,dr,mij,aux,ind1=nr+1,ind2=0;
if( l1>l2 )
aux= l1,l1=l2,l2=aux;
st=1;
dr=nr;
while( st<=dr )
{
mij= (st+dr)/2;
if( v[mij].x<f || (v[mij].x==f && v[mij].y<l1) )
st=++mij;
else
{
ind1=mij;
dr=--mij;
}
}
st=1;
dr=nr;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij].x>f || (v[mij].x==f && v[mij].y>l2))
dr=mij-1;
else
{
ind2=mij;
st=mij+1;
}
}
return max( ind2-ind1+1, 0 );
}
int main ()
{
int px, py, a, b, ind;
char dir;
long long l;
in >> N >> M;
int i, j;
for( i=1; i<=N; ++i )
{
in >> a >> b;
in.get();
adaug( a, b );
}
sort( qx+1, qx+nr+1 );
for( i=2, j=1; i<=nr; ++i )
{
if( qx[i]!=qx[j] )
qx[++j]=qx[i];
}
nr=j;
for( i= 1,j= 0; i<=nr; ++i )
{
if( qx[i]!=make_pair(0,0) )
qx[++j]=qx[i];
}
nr=j;
for( i=1; i<=nr; ++i )
{
qy[i].x= qx[i].y;
qy[i].y= qx[i].x;
}
sort( qy+1, qy+nr+1 );
px= 0;
py= 0;
for( i= 1; i<=M; ++i )
{
in >> dir;
in.get();
in >> l;
in.get();
if(dir=='N')
ind=0;
else if(dir=='E')
ind=1;
else if(dir=='S')
ind=2;
else ind= 3;
if( dir=='S' || dir=='N' )
sol+= caut_binar( qx, px, py+dy[ind], py+dy[ind]*l );
else
sol+=caut_binar( qy, py, px+dx[ind], px+dx[ind]*l );
px+= dx[ind]*l;
py+= dy[ind]*l;
}
out << sol;
return 0;
}