Cod sursa(job #830614)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 7 decembrie 2012 11:00:31
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.84 kb
#include<cstdio>
#include<string.h>
#include<algorithm>

using namespace std;

struct point{
	int x;
	int y;
} a[1300001],b[1300001],sx[1300001],sy[1300001];
int i,j,n,m,p,nr,w,t,x,y,pozx,pozy,dist,inceput,final,solutie;
int semn[256];
char dir;

bool cmpA (point i,point j){
	return (i.x<j.x || (i.x==j.x&&i.y<j.y)); 
}

bool cmpY (point i,point j){
	return (i.y<j.y || (i.y==j.y&&i.x<j.x));
}

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 ){
				nr++;
				a[nr].x=x+i;
				a[nr].y=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[m].x>x)
             u=m-1;
        else if(sx[m].x<x)
                p=m+1;
        else {
            if((dir=='N'&&sx[m].y>=y&&sy[m].y<=y+dist*semn[dir])||(dir=='S'&&sx[m].y<=y&&sx[m].y>=y+dist*semn[dir]))
                {
                    gasit=m;
                    u=m-1;
                }
            else p=m+1;
            }
    }
	if(gasit!=0)
		return gasit;
	return -1;
}
 
int cautax1(int x,int y){
    int p,u,m,gasit=0;
    p=1;
    u=nr;
    while(p<=u){
        m=(p+u)/2;
        if(sx[m].x>x)
             u=m-1;
        else if(sx[m].x<x)
                p=m+1;
        else {
            if(sx[m].y<=y||sx[m].y<y-dist*semn[dir])
                {
                    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[m].y>y)
             u=m-1;
        else if(sy[m].y<y)
                p=m+1;
        else {
            if((dir=='E'&&sy[m].x>=x&&sy[m].x<=x+dist*semn[dir])||(dir=='V'&&sy[m].x<=x&&sy[m].x>=x+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=1;
    u=nr;
    while(p<=u){
        m=(p+u)/2;
        if(sy[m].y>y)
             u=m-1;
        else if(sy[m].y<y)
                p=m+1;
        else {
            if(sy[m].x<=x||sy[m].x<x-dist*semn[dir])
                {
                    gasit=m;
                    p=m+1;
                }
            else u=m-1;
            }
    }
return gasit;
}
 
 
int main(){
	
	freopen("zc.in","r",stdin);
	freopen("zc.out","w",stdout);

	semn['N'] =  1;
	semn['S'] = -1;
	semn['E'] =  1;
	semn['V'] = -1;
	scanf("%d%d",&n,&m);

	//adaugam in vector toate punctele capcana
	for(i=1;i<=n;i++){
		scanf("%d%d",&x,&y);
		fill(x,y);
	}

	//sort a
	sort(a+1,a+nr+1,cmpA);  

	n=nr;
	nr=0;

	a[0].x=0;
	a[0].y=0;
	for(i=1;i<=n;i++)
		if(a[i].x!=sx[nr].x || a[i].y!=sx[nr].y ){
			sx[++nr].x=a[i].x;
			sx[nr].y=a[i].y;

			sy[nr]=sx[nr];
		}

	//sort by Y
	sort(sy+1,sy+nr+1,cmpY);

	pozx=0;
	pozy=0;
	for(i=1;i<=m;i++){
		dir=' ';
		while(dir=='\n'||dir==' ')
			scanf("%c",&dir);
			scanf("%d",&dist);
			if(dir=='N'||dir=='S'){
				inceput = cautax(pozx,pozy);
				pozy   += dist*semn[dir];
				if(inceput!=-1){
					final=cautax1(pozx,pozy);
					if(sx[inceput].y==pozy-dist*semn[dir])
						solutie--;
					if(final>inceput)
						solutie+=final-inceput+1;
					else
						solutie+=-final+inceput+1;
				}
			}
			else {
				inceput=cautay(pozx,pozy);
				pozx+=dist*semn[dir];
				if(inceput!=-1){
					final=cautay1(pozx,pozy);
					if(sy[inceput].x==pozx-dist*semn[dir])
						solutie--;
					if(final>inceput)
						solutie+=final-inceput+1;
					else
						solutie+=-final+inceput+1;
				}
			}
	}
	printf("%d",solutie);
	return 0;
}