Cod sursa(job #362983)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 11 noiembrie 2009 14:42:01
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.62 kb
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

#define FOR(i,a,b)for(i=(a);i<=(b);++i)
#define inf 2000000002
#define mkp make_pair
#define pb push_back
#define nm 1300005
#define x first
#define y second

int N,M;

char out[nm];

vector<pair<int,int> >VX,VY,NX,NY;

void proc(int xx,int yy)
{
    VX.pb(mkp(xx,yy));
    VY.pb(mkp(yy,xx));
}

void refa()
{
     int i;
     
     FOR(i,1,VX.size()-1)
       if(VX[i].x==VX[i-1].x && VX[i].y==VX[i-1].y) out[i]=1;
     
     FOR(i,0,VX.size()-1)
       if(!out[i]) NX.pb(VX[i]);
     
     memset(out,0,sizeof(out));
     
     FOR(i,1,VY.size()-1)
       if(VY[i].x==VY[i-1].x && VY[i].y==VY[i-1].y) out[i]=1;
     
     FOR(i,0,VY.size()-1)
       if(!out[i]) NY.pb(VY[i]);  
       
}

int bsx(int cx,int sy,int ey)
{
    int st=0,dr=NX.size()-1,start,stop;
    
    while(st<dr)
    {
      int mij=(st+dr)/2;
      if(NX[mij].x<cx || (NX[mij].x==cx && NX[mij].y<sy)) st=mij+1;
      else dr=mij;
    }
    
    if(NX[st].x==cx && NX[st].y>=sy) start=st; 
    else return 0;
   
     st=0,dr=NX.size()-1;
     
     while(st<dr-1)
     {
       int mij=(st+dr)/2;
       if(NX[mij].x>cx || (NX[mij].x==cx && NX[mij].y>ey)) dr=mij-1;
       else st=mij;
     }
     
     if(NX[dr].x==cx && NX[dr].y<=ey) st=dr;  
     else if(NX[st].x==cx && NX[st].y<=ey);
          else return 0; 
     
     stop=st;
     
     return stop-start+1;     
     
}

int bsy(int cy,int sx,int ex)
{
    int st=0,dr=NY.size()-1,start,stop;
    
    while(st<dr)
    {
      int mij=(st+dr)/2;
      if(NY[mij].x<cy || (NY[mij].x==cy && NY[mij].y<sx)) st=mij+1;
      else dr=mij;
    }
    
    if(NY[st].x==cy && NY[st].y>=sx) start=st; 
    else return 0;
    
    st=0,dr=NY.size()-1;
     
     while(st<dr-1)
     {
       int mij=(st+dr)/2;
       if(NY[mij].x>cy || (NY[mij].x==cy && NY[mij].y>ex)) dr=mij-1;
       else st=mij;
     }
     
     if(NY[dr].x==cy && NY[dr].y<=ex) st=dr;  
     else if(NY[st].x==cy && NY[st].y<=ex);
          else return 0; 
     
     stop=st;
     
     return stop-start+1;
}

int main()
{
    int i,xx,yy,pasi,ys,ye,ans=0;
    
    char dir;
    
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);
    
    scanf("%d %d",&N,&M);
    
    FOR(i,1,N)
    {
      scanf("%d %d\n",&xx,&yy);
      
      proc(xx,yy+2);
      proc(xx,yy+1);
      proc(xx,yy);
      proc(xx,yy-1);
      proc(xx,yy-2);
      
      proc(xx-1,yy-1);
      proc(xx-1,yy);
      proc(xx-1,yy+1);
      
      proc(xx-2,yy);
      
      proc(xx+1,yy-1);
      proc(xx+1,yy);
      proc(xx+1,yy+1);
      
      proc(xx+2,yy);
    }
    
    sort(VX.begin(),VX.end());
    sort(VY.begin(),VY.end());
    
    refa();
    
    int sx=0,sy=0;
    
    FOR(i,1,M)
    {
      scanf("%c %d\n",&dir,&pasi);
      
      if(dir=='N')
      {
        ys=sy+1;
        ye=sy+pasi;
        
        ans+=bsx(sx,ys,ye);
        
        sy=ye;
        
        continue;
      }
      
      if(dir=='S')
      {
        ys=sy-1;
        ye=sy-pasi;
        
        ans+=bsx(sx,ye,ys);
        
        sy=ye;
        
        continue;
      }
      
      if(dir=='V')
      {
        ans+=bsy(sy,sx-pasi,sx-1);          
                  
        sx-=pasi;
        continue;  
      }
      
      if(dir=='E')
      {
        ans+=bsy(sy,sx+1,sx+pasi);         
                  
        sx+=pasi;
        continue;
      }
    }
    
    printf("%d",ans);
    
    return 0;
}