Cod sursa(job #359076)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 25 octombrie 2009 17:48:17
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

struct coord{
	int x,y;
};

coord d;
vector<coord> a,b;
int dirx[13]={-2,-1,-1,-1,0,0,0,0,0,1,1,1,2};
int diry[13]={0,-1,0,1,-2,-1,0,1,2,-1,0,1,0};
int i,j,n,m,x,y,q,w,e,r;
unsigned int nr;
long long sum,rez;
char ch;

bool cmp(coord a, coord b){
	if (a.x==b.x)
		return a.y<b.y;
	return a.x<b.x;
}

int cautx1(int x, int st, int dr)
{
	int sol=n;
	int mij;
	while (st<=dr){
		mij=(st+dr)/2;
		if (a[mij].x>=x){
			sol=mij;
			dr=mij-1;
		}
		else
			st=mij+1;
	}
	return sol;
}

int cauty1(int x, int st, int dr)
{
	int sol=n;
	int mij;
	while (st<=dr){
		mij=(st+dr)/2;
		if (a[mij].y>=x){
			sol=mij;
			dr=mij-1;
		}
		else
			st=mij+1;
	}
	return sol;
}

int cautx2(int x, int st, int dr)
{
	int sol=n;
	int mij;
	while (st<=dr){
		mij=(st+dr)/2;
		if (b[mij].x>=x){
			sol=mij;
			dr=mij-1;
		}
		else
			st=mij+1;
	}
	return sol;
}
int cauty2(int x, int st, int dr)
{
	int sol=n;
	int mij;
	while (st<=dr){
		mij=(st+dr)/2;
		if (b[mij].y>=x){
			sol=mij;
			dr=mij-1;
		}
		else
			st=mij+1;
	}
	return sol;
}

int main()
{
	freopen("zc.in","r",stdin);
	freopen("zc.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	for (i=1; i<=n; i++){
		scanf("%d %d\n",&x,&y);
		for (j=0; j<13; j++){
			d.x=x+dirx[j];
			d.y=y+diry[j];
			b.push_back(d);
		}
	}
	sort(b.begin() , b.end(),cmp);
	a.push_back(b[0]);
	for (i=1; i<b.size(); i++)
		if (!(b[i].x==b[i-1].x && b[i].y==b[i-1].y))
			a.push_back(b[i]);
	n=a.size();
	b.clear();
	for (i=0; i<a.size(); i++){
		d.x=a[i].y;
		d.y=a[i].x;
		b.push_back(d);
	}
	x=y=0; d.x=d.y=2147483640;
	sort(b.begin(), b.end(), cmp);
	b.push_back(d); a.push_back(d);
	d.x=d.y=0;
	for (i=1; i<=m; i++){
		scanf("%c %d\n",&ch,&nr);
		if (ch=='N'){
			d.x=x;
			nr=nr+y;
			d.y=nr;
			q=cautx1(x,0,n-1);
			if (a[q].x==x){
				w=cautx1(x+1,q,n-1)-1;
				e=cauty1(y,q,w);
				if (a[e].x==x && a[e].y==y)
					sum--;
				r=cauty1(d.y+1,q,w);
				if (r==n)
					r=w;
				else
					r--;
				if (e!=n){
					rez=r-e+1;
					sum=sum + rez;
				}
			}
			y=nr;
		}
		if (ch=='S'){
			d.x=x;
			d.y=y;
			y-=nr;
			q=cautx1(x,0,n-1);
			if (a[q].x==x){
				w=cautx1(x+1,q,n-1)-1;
				e=cauty1(y,q,w);
				r=cauty1(d.y+1,q,w);
				if (r==n)
					r=w;
				else
					r--;
				if ((r>=0) && a[r].x==d.x && a[r].y==d.y)
					sum--;
				if (e!=n){
					rez=r-e+1;
					sum=sum + rez;
				}
			}
		}
		if (ch=='E'){
			nr=nr+x;
			d.x=nr;
			d.y=y;
			q=cautx2(y,0,n-1);
			if (b[q].x==y){
				w=cautx2(y+1,q,n-1)-1;
				e=cauty2(x,q,w);
				if (b[e].x==y && b[e].y==x)
					sum--;
				r=cauty2(d.x+1,q,w);
				if (r==n)
					r=w;
				else
					r--;
				if (e!=n){
					rez=r-e+1;
					sum=sum+rez;
				}
			}
			x=nr;
		}
		if (ch=='V'){
			d.x=x;
			d.y=y;
			x-=nr;
			q=cautx2(y,0,n-1);
			if (b[q].x==y){
				w=cautx2(y+1,q,n-1)-1;
				e=cauty2(x,q,w);
				r=cauty2(d.x+1,q,w);
				if (r==n)
					r=w;
				else
					r--;
				if ((r>=0) && b[r].x==d.y && b[r].y==d.x)
					sum--;
				if (e!=n){
					rez=r-e+1;
					sum=sum+rez;
				}
			}
		}
	}
	printf("%lld\n",sum);
	return 0;
}