Cod sursa(job #595700)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 13 iunie 2011 16:06:23
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

struct punct {
	int x,y;
};

punct poz[2000000];
int n,m,nr,dist,praf,nrr;
char c;

void ver(int i) {
	if(i<0)
		--nr;
}

bool cmp(punct a, punct b) {
	if(a.x>b.x)
		return 0;
	if(a.x<b.x)
		return 1;
	if(a.y>b.y)
		return 0;
	return 1;
}

int main() {
	int i,j,x,y,cx,cy,k,pas,dir;
	punct p;
	
	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",&y,&x);
		poz[++nr].x=x; poz[nr].y=y;
		poz[++nr].x=x; poz[nr].y=y-1; ver(y-1);
		poz[++nr].x=x; poz[nr].y=y-2; ver(y-2);
		poz[++nr].x=x; poz[nr].y=y+1;
		poz[++nr].x=x; poz[nr].y=y+2;
		poz[++nr].x=x-2; poz[nr].y=y; ver(x-2);
		poz[++nr].x=x+2; poz[nr].y=y;
		poz[++nr].x=x-1; poz[nr].y=y;
		poz[++nr].x=x-1; poz[nr].y=y-1;
		if(x==1 || y==1)
			--nr;
		poz[++nr].x=x-1; poz[nr].y=y+1;
		poz[++nr].x=x+1; poz[nr].y=y+1;
		poz[++nr].x=x+1; poz[nr].y=y;
		poz[++nr].x=x+1; poz[nr].y=y-1; ver(y-1);
	}
	sort(poz,poz+nr+1,cmp);
	
	for(i=1;i<=nr;++i)
		if(poz[i].x!=poz[i-1].x || poz[i].y!=poz[i-1].y)
			poz[++nrr]=poz[i];
	nr=nrr;
	
	cx=0; cy=0;
	p.x=cx; p.y=cy;
	for(i=1;i<=m;++i) {
		scanf("%c %d\n",&c,&dist);
		if(c=='N')
			dir=1;
		if(c=='S')
			dir=3;
		if(c=='E')
			dir=0;
		if(c=='V')
			dir=2;
		
		for(j=1;j<=dist;++j) {
			p.x+=dx[dir];
			p.y+=dy[dir];
			pas=1<<30;
			for(k=0;pas!=0;pas>>=1) {
				if(k+pas<=nr && cmp(poz[k+pas],p))
					k+=pas;
			}
			if(p.x==poz[k].x && p.y==poz[k].y)
				++praf;
		}
	}
	
	printf("%d\n",praf);
	return 0;
}