Cod sursa(job #42377)

Utilizator cos_minBondane Cosmin cos_min Data 29 martie 2007 09:45:04
Problema Zota & Chidil Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.66 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];
char ac[dim];
int px[13*dim], py[13*dim], a[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, };   
const int dj[] = { 0, -1, 0, 1, -1, 0, 1, 0, -2, -1, 1, 2, };

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);
     
     t = N;
     for ( int i = 1; i <= N; i++ )
     {
         scanf("%d%d", &py[i], &px[i]);
         
         for ( int k = 0; k < 12; k++ )
         {
             t++;
             py[t] = py[i] + di[k];
             px[t] = px[i] + dj[k];
         }
     }
     
     N = t;
     
     for ( int i = 1; i <= M; i++ )
     {
         scanf("\n%c%d", &ac[i], &a[i] );
     }
}

void Solve()
{
     Qsort(1,N);
     
     map<char,int> px1;
     map<char,int> py1;

     px1['N'] = 1; py1['N'] = 0;
     px1['S'] = -1; py1['S'] = 0;
     px1['V'] = 0; py1['V'] = -1;
     px1['E'] = 0; py1['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]; j++ )
         {
             ivec = ivec + px1[ac[i]];
             jvec = jvec + py1[ac[i]];  
            // for ( int k = 0; k < 13; k++ )
             {
                 if ( BinaryS(ivec,jvec) ) 
                 {
                    //  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;
     int pivot1 = px[st];
     int pivot2 = py[st];
     
     while ( i <= j )
     {
           do { i++; } while ( px[i] < pivot1 || ( pivot1 == px[i] && py[i] < pivot2 ) );
           do { j--; } while ( px[j] > pivot1 || ( pivot1 == px[j] && py[j] > pivot2 ) );
           
           if ( i <= j )
           {
                int aux = px[i];
                px[i] = px[j];
                px[j] = aux;
                int aux2 = py[i];
                py[i] = py[j];
                py[j] = aux2;
           }
     }
     
     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;
    
    while ( st <= dr )
    {
          t+=1;
          int mij = (st+dr)>>1;
          if ( px[mij] > i  ) 
          {
               dr = mij-1;
          }
          else
          {
              if ( i > px[mij]  )
              {
                   st = mij+1;
              }
              else 
              if ( px[mij] == i ) 
              {
                   if ( py[mij] > j ) 
                   {
                      dr = mij-1;
                   }
                   else 
                   if ( j > py[mij] )
                   {
                      st = mij+1;
                   }
                   
                   if ( py[mij] == j ) 
                   {
                        ok = 1; 
                        st = dr+1; 
                        break;
                   }
              }
          }
    }
    
    return ok;
}