Cod sursa(job #42216)

Utilizator cos_minBondane Cosmin cos_min Data 28 martie 2007 23:07:54
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.04 kb
#include <stdio.h>
#include <map>
using namespace std;

#define in "zc.in"
#define out "zc.out"
#define dim 100001

int N, M;
struct mutare { char c; int nr; } a[dim];
struct punct { int x, y; } p[dim];
int t=0;

//const int di[] = { 2, 1, -2, -1, 1, 1, -1, -1, 0, 0, 0, 0 };
//const int dj[] = { 0, 0, 0, 0, 1, -1, -1, 1, -1, -2, 1, 2 };

const int di[] = { -2, -1, -1, -1, 1, 1, 1, 2, 0, 0, 0, 0, 0 };   
const int dj[] = { 0, -1, 0, 1, -1, 0, 1, 0, -2, -1, 1, 2, 0 };

void Qsort(int,int);
int BinaryS(int,int);
void Solve();
void ReadData();

int main()
{
    ReadData();
    Solve();
    
    return 0;
}

void ReadData()
{
     
     freopen(out,"w",stdout);
     
     freopen(in,"r",stdin);
     scanf("%d%d", &N, &M);
     for ( int i = 1; i <= N; i++ )
     {
         scanf("%d%d", &p[i].y, &p[i].x);
     }
     
     for ( int i = 1; i <= M; i++ )
     {
         scanf("\n%c%d", &a[i].c, &a[i].nr );
     }
}

void Solve()
{
     
     Qsort(1,N);
     
     map<char,int> px;
     map<char,int> py;

     px['N'] = 1; py['N'] = 0;
     px['S'] = -1; py['S'] = 0;
     px['V'] = 0; py['V'] = -1;
     px['E'] = 0; py['E'] = 1;
     
     int ivec, jvec;
     long long total = 0;
     
     ivec = jvec = 0;
     
     for ( int i = 1; i <= M; i++ )
     {
         for ( int j = 1; j <= a[i].nr; j++ )
         {
             ivec = ivec + px[a[i].c];
             jvec = jvec + py[a[i].c];  
             for ( int k = 0; k < 13; k++ )
             {
                 if ( BinaryS(ivec+di[k],jvec+dj[k]) ) 
                 {
                    //  printf("%d %d\n",ivec,jvec); 
                      total += 1;
                 }
             }
         }
     }
     
    // printf("%lld\n", t);
     printf("%lld", total);
}

void Qsort(int st, int dr)
{
     int i = st-1;
     int j = dr+1;
     punct pivot = p[st];
     
     while ( i <= j )
     {
           do { i++; } while ( p[i].x < pivot.x || ( pivot.x == p[i].x && p[i].y < pivot.y ) );
           do { j--; } while ( p[j].x > pivot.x || ( pivot.x == p[j].x && p[j].y > pivot.y ) );
           
           if ( i <= j )
           {
                punct aux = p[i];
                p[i] = p[j];
                p[j] = aux;
           }
     }
     
     if ( st < j ) Qsort(st,j);
     if ( i < dr ) Qsort(i,dr);
}

int BinaryS(int i, int j)
{
    int ok = 0;
    int st = 1, dr = N;
    int mij, val;
    
    while ( st < dr )
    {
         // t += 1;
          mij = (st+dr)>>1;
          if ( p[mij].x > i  ) 
          {
               val = mij>>1;
               if ( p[val].x > i )   dr = val-1;
               else                  st = val, dr = mij-1;
          }
          else
          {
              if ( i > p[mij].x  )
              {
                   val = (dr+mij)>>1;
                   if ( i > p[val].x ) st = val+1;
                   else                dr = val, st = mij;
              }
              else 
              if ( p[mij].x == i ) 
              {
                   if ( p[mij].y > j ) 
                   {
                        val = mij>>1;
                        if ( p[val].y > j )   dr = val-1;
                        else                  st = val, dr = mij-1;
                       // dr = mij-1;
                   }
                   else 
                   if ( j > p[mij].y )
                   {
                      val = (dr+mij)>>1;
                      if ( j > p[val].y ) st = val+1;
                      else                dr = val, st = mij;
                    //  st = mij + 1;
                   }
                   
                   if ( p[mij].y == j ) 
                   {
                        ok = 1; 
                        st = dr+1; 
                        break;
                   }
              }
          }
          
          if ( st == dr && p[st].x == i && p[st].y == j ) ok = 1;
          else                                            ok = 0; 
    }
    
    return ok;
}