Cod sursa(job #66386)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 18 iunie 2007 00:28:01
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 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,li1=0,li2=0;
int m,lo,hi,st,dr;
dot tmp;
char 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);

	x=0; y=0;

	for (i=0;i<M;++i) {
		fgetc(stdin);
		scanf("%c%d",&dir,&len);	
		x1=x; y1=y;
		if ((dir=='N' || dir=='S') && len) {
			if (dir=='N') {
				y1+=len;
				++y;
				li1=y; li2=y1;
			}
			if (dir=='S') {
				y1-=len;
				--y;
				li1=y1; li2=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 < li1 )
					        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 > li2)
						hi=m-1;
					else
						lo=m+1;
				else
					lo=m+1;
			}	
			dr=hi;
			
			if (st<=dr)
				ret+=(dr-st+1);
			
		}
		if ((dir=='E' || dir=='V') && len) {
			if (dir=='E') {
				x1+=len;
				++x;
				li1=x; li2=x1;
			}
			if (dir=='V') {
				x1-=len;
				--x;
				li1=x1; li2=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 < li1 )
					        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 > li2)
						hi=m-1;
					else
						lo=m+1;
				else
					lo=m+1;
			}	
			dr=hi;
			
			if (st<=dr)
				ret+=(dr-st+1);
			
		}

		x=x1; y=y1;
	}

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