Cod sursa(job #66383)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 17 iunie 2007 23:49:36
Problema Zota & Chidil Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define fin  "zc.in"
#define fout "zc.out"

using namespace std;

struct dot { int x,y; };

vector <dot> vx,vy;
int N,M;
long long ret;

bool cmpx(dot a,dot b) {
	if (a.x < b.x)
		return 1;
	else
	if (a.x == b.x && a.y < b.y)
		return 1;
	else
		return 0;
}

bool cmpy(dot a,dot b) {
	if (a.y < b.y)
		return 1;
	else
	if (a.y == b.y && a.x < b.x)
		return 1;
	else
		return 0;
}


int main() {
int i,j,x,y,x1,y1,len;
int m,lo,hi,st,dr;
dot tmp;
char c,dir;
	freopen(fin,"r",stdin); freopen(fout,"w",stdout);

	scanf("%d%d",&N,&M);
	
	for (i=0;i<N;++i) {
		scanf("%d%d",&x,&y);
		for (j=x-2;j<=x+2;++j) {
			tmp.x=j; tmp.y=y;
			vx.push_back(tmp);		
		}
		for (j=x-1;j<=x+1;++j) {
			tmp.x=j; tmp.y=y-1;
			vx.push_back(tmp);	
			tmp.y=y+1;
			vx.push_back(tmp);	
		}
		tmp.x=x; tmp.y=y+2;
		vx.push_back(tmp);
		tmp.x=x; tmp.y=y-2;
		vx.push_back(tmp);
	}
	
	sort(vx.begin(),vx.end(),cmpx);

	for (i=0;i<(int)vx.size();++i)
		if (i==0 || !(vx[i].x==vx[i-1].x && vx[i].y==vx[i-1].y))
		if (vx[i].x!=0 || vx[i].y!=0)	
			vy.push_back(vx[i]);
	vx.clear();
	for (i=0;i<(int)vy.size();++i)
		vx.push_back(vy[i]);

	sort(vy.begin(),vy.end(),cmpy);
	sort(vx.begin(),vx.end(),cmpx);
/*
	for (i=0;i<vx.size();++i)
		fprintf(stderr,"(%d %d) ",vx[i].x,vx[i].y);
	fprintf(stderr,"\n");
	for (i=0;i<vy.size();++i)
		fprintf(stderr,"(%d %d) ",vy[i].x,vy[i].y);
*/
	x=0; y=0;

	fgetc(stdin);

	for (i=0;i<M;++i) {
		len=0; 
		dir=fgetc(stdin);
		do {	
			c=fgetc(stdin);
			if (c>='0' && c<='9')
				len=len*10+c-'0';
		} while (c!='\n');
		
		//fprintf(stderr,"%c %d\n",dir,len);

		x1=x; y1=y;
		if ((dir=='N' || dir=='S') && len) {
			if (dir=='N') {
				y1+=len;
				++y;
			}
			if (dir=='S') {
				y1-=len;
				--y;
			}
			lo=0; hi=(int)vx.size()-1;
			while (lo<=hi) {
				m=(lo+hi)/2;
				if ( vx[m].x < x1) 
					lo=m+1;
				else
				if ( vx[m].x == x1 )
					if ( vx[m].y < y )
					        lo=m+1;
					else
						hi=m-1;	
				else
					hi=m-1;
			}	
			st=lo;

			lo=st; hi=(int)vx.size()-1;
			while (lo<=hi) {
				m=(lo+hi)/2;
				if ( vx[m].x > x1 )
					hi=m-1;
				else
				if ( vx[m].x == x1 )
					if (vx[m].y > y1)
						hi=m-1;
					else
						lo=m+1;
				else
					lo=m+1;
			}	
			dr=hi;
			
			if (st<=dr)
				ret+=(dr-st+1);
			
			//fprintf(stderr,"%d %d: %d %d\n",x1,y1,st,dr);
		}
		if ((dir=='E' || dir=='V') && len) {
			if (dir=='E') {
				x1+=len;
				++x;
			}
			if (dir=='V') {
				x1-=len;
				--x;
			}
			lo=0; hi=(int)vy.size()-1;
			while (lo<=hi) {
				m=(lo+hi)/2;
				if ( vy[m].y < y1) 
					lo=m+1;
				else
				if ( vy[m].y == y1 )
					if ( vy[m].x < x )
					        lo=m+1;
					else
						hi=m-1;	
				else
					hi=m-1;
			}	
			st=lo;

			lo=st; hi=(int)vy.size()-1;
			while (lo<=hi) {
				m=(lo+hi)/2;
				if ( vy[m].y > y1 )
					hi=m-1;
				else
				if ( vy[m].y == y1 )
					if (vy[m].x > x1)
						hi=m-1;
					else
						lo=m+1;
				else
					lo=m+1;
			}	
			dr=hi;
			
			if (st<=dr)
				ret+=(dr-st+1);
			
			//fprintf(stderr,"%d %d: %d %d\n",x1,y1,st,dr);

		}

		x=x1; y=y1;
	}

	printf("%lld\n",ret);
	return 0;
}