Cod sursa(job #425631)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 25 martie 2010 21:53:34
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.18 kb
#include<stdio.h>
#include<string.h>
FILE *f=fopen("zc.in","r");
FILE *g=fopen("zc.out","w");
int a[2][1300001],b[2][1300001],sx[2][1300001],sy[2][1300001],i,j,n,m,p,nr,w,t,x,y,pozx,pozy,dist,inceput,final,solutie;
int semn[256];
char dir;
void asort(){
	for(i=1;i<=nr;i++)
		for(j=1;j<=nr;j++)
			if(a[0][i]<a[0][j] || (a[0][i]==a[0][j]&&a[1][i]<a[1][j]) )
			{  t=a[0][i];
			   a[0][i]=a[0][j];
			   a[0][j]=t;
			    t=a[1][i];
			   a[1][i]=a[1][j];
			   a[1][j]=t;
			}
	
}

void sysort(){
	for(i=1;i<=nr;i++)
		for(j=1;j<=nr;j++)
			if(sy[1][i]<sy[1][j] || (sy[1][i]==sy[1][j]&&sy[0][i]<sy[0][j]) )
			{  t=sy[0][i];
			   sy[0][i]=sy[0][j];
			   sy[0][j]=t;
			    t=sy[1][i];
			   sy[1][i]=sy[1][j];
			   sy[1][j]=t;
			}
	
}
void fill(int x,int y){
	for(int j=-2;j<=2;j++)
	{  w=j;
	   if(w<0)
		    w=-w;
	   w=2-w;
		for(int i=-w;i<=w;i++)
			if((x+i!=0 || y+j!=0 )&& x+i>=0 && y+i >=0)
			{ nr++;
			   a[0][nr]=x+i;
			   a[1][nr]=y+j;
			}
	}
}

int cautax(int x,int y){
	int p,u,m,gasit=0;
	p=1;
	u=nr;
	while(p<=u){
		m=(p+u)/2;
		if(sx[0][m]>x)
			 u=m-1;
		else if(sx[0][m]<x)
			    p=m+1;
		else {
			if(sx[1][m]>y && sx[1][m] <sx[1][m]<(pozy+dist*semn[dir]))
				{
					gasit=m;
					u=m-1;
				}
			else p=m+1;	
			}
	}
if(gasit!=0)
	return gasit;
else return -1;	
}

int cautax1(int x,int y){
	int p,u,m,gasit=0;
	p=inceput;
	u=nr;
	while(p<=u){
		m=(p+u)/2;
		if(sx[0][m]>x)
			 u=m-1;
		else if(sx[0][m]<x)
			    p=m+1;
		else {
			if(sx[1][m]<=y)
				{
					gasit=m;
					p=m+1;
				}
			else u=m-1;	
			}
	}
return gasit;
}

int cautay(int x,int y){
	int p,u,m,gasit=0;
	p=1;
	u=nr;
	while(p<=u){
		m=(p+u)/2;
		if(sy[1][m]>y)
			 u=m-1;
		else if(sy[1][m]<y)
			    p=m+1;
		else {
			if(sy[0][m]>x && sy[0][m]<(pozx+dist*semn[dir]))
				{
					gasit=m;
					u=m-1;
				}
			else p=m+1;	
			}
	}
if(gasit!=0)
	return gasit;
else return -1;	
}

int cautay1(int x,int y){
	int p,u,m,gasit=0;
	p=inceput;
	u=nr;
	while(p<=u){
		m=(p+u)/2;
		if(sy[1][m]>y)
			 u=m-1;
		else if(sy[1][m]<y)
			    p=m+1;
		else {
			if(sy[0][m]<=x)
				{
					gasit=m;
					p=m+1;
				}
			else u=m-1;	
			}
	}
return gasit;
}


int main(){
semn['N']=1;
semn['S']=-1;
semn['E']=1;
semn['V']=-1;
	fscanf(f,"%d%d",&n,&m);
//adaugam in vector toate punctele capcana
for(i=1;i<=n;i++){
	fscanf(f,"%d%d",&x,&y);
	fill(x,y);
}
asort();
n=nr;
nr=0;
//hash
a[0][0]=0;
a[1][0]=0;
for(i=1;i<=n;i++)
	if(a[0][i]!=sx[0][nr] || a[1][i]!=sx[1][nr] )
	{  sx[0][++nr]=a[0][i];
	   sx[1][nr]=a[1][i];
	}
memcpy(sy[0],sx[0],sizeof(sx[0]));
memcpy(sy[1],sx[1],sizeof(sx[1]));
sysort();
pozx=0;
pozy=0;
for(i=1;i<=m;i++){
	dir=' ';
	while(dir=='\n'||dir==' ')
		 fscanf(f,"%c",&dir);
	fscanf(f,"%d",&dist);
	if(dir=='N'||dir=='S'){
	    inceput=cautax(pozx,pozy);
		pozy+=dist*semn[dir];
	 if(inceput!=-1){
		 final=cautax1(pozx,pozy);
		 solutie+=final-inceput+1;
	 }
	}
	else {
	  inceput=cautay(pozx,pozy);
	  pozx+=dist*semn[dir];
	  if(inceput!=-1){
		final=cautay1(pozx,pozy);
		solutie+=final-inceput+1;
	  }
		
	}
	
	
}
fprintf(g,"%d",solutie);
return 0;
}