Cod sursa(job #42177)

Utilizator TabaraTabara Mihai Tabara Data 28 martie 2007 22:05:12
Problema Zota & Chidil Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.2 kb
/*
Autor: Mihai Tabara
Lang:C++
Prog: Zota&Chidil
Punctaj: 40
Sursa: http://infoarena.ro/arhiva/zc
*/
#include <stdio.h>
#include <math.h>

#define in "zc.in"
#define out "zc.out"
#define NMAX 1200001

#define eps 1e-5

struct Punct {
       int x;
       int y;
} a[NMAX], aux;

int n, m, ind, nn, nrsol;
int ip, jp, iv, jv, x, y;
bool gasit;

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

void BS( int, int );
void Read();
void Solve();
void GO( char c, int val );
void QSort( int st, int dr );
inline int Ok( int i, int j );

FILE *fout = fopen ( out, "w" );

int main()
{
    Read();
    /*
    int i;
    for ( i = 1; i <= ind; ++i )
        fprintf( fout, "%d %d\n", a[i].x, a[i].y );*/
    fprintf( fout, "%d\n", nrsol );
    fclose ( fout );
    return 0;
}

void Read()
{
     FILE *fin = fopen ( in, "r" );
     fscanf ( fin, "%d %d\n", &n, &m );
     ind = 1;
     nn = n;
     int cx, cy, i;
     for ( i = 1; i <= n; ++i )
     {
         fscanf(fin, "%d %d\n", &cx, &cy );
         if ( cx == 0 && cy == 0 ) 
         {
              nn--;
              continue;
         }
         a[ind].x = cx;
         a[ind].y = cy;
         ind++;
     }
     n = nn;
     ind--;
     Solve();
     iv = jv = x = y = ip = jp = 0;
     char ch;
     int val;
     for ( i = 1; i <= m; ++i )
     {
         fscanf( fin, "%c %d\n", &ch, &val );
         //fprintf( fout, "%c %d\n", ch, val );
         GO ( ch, val );
     }
     fclose ( fin );
}

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

void Solve()
{
     int i, d;
     x = y = iv = jv = 0;
     for ( i = 1; i <= n; ++i )
     {
         x = a[i].x, y = a[i].y;
         for ( d = 0; d < 12; ++d )
         {
             iv = x + di[d];
             jv = y + dj[d];
             if ( Ok(iv,jv) )
             {
                  ind++;
                  a[ind].x = iv;
                  a[ind].y = jv;
             }
         }
     }
     QSort( 1, ind );
}
        
       
inline int Ok( int i, int j )
{
    if ( i == 0 && j == 0 ) return 0;
    return 1;
}


void GO( char c, int val )
{
     int i;
     if ( c == 'N' ) 
     {
          gasit = false;
          iv = ip;
          jv = jp+1;
          BS( iv, jv );
          if ( gasit == true )
          {
               nrsol++;
               //fprintf( fout, "%d %d\n", iv, jv );
          }
          //fprintf( fout, "%d %d\n", iv, jv );
          for ( i = 2; i <= val; ++i )
          {
              iv = iv;
              jv = jv+1;
              gasit = false;
              BS( iv, jv );
              if ( gasit == true )
              {
                   nrsol++;
                   //fprintf( fout, "%d %d\n", iv, jv );
               }
              //fprintf( fout, "%d %d\n", iv, jv );
          }
          ip = iv;
          jp = jv;
     }
     if ( c == 'S' ) 
     {
          iv = ip;
          jv = jp-1;
          gasit = false;
          BS( iv, jv );
          if ( gasit == true )
          {
                nrsol++;
                //fprintf( fout, "%d %d\n", iv, jv );
          }
          //fprintf( fout, "%d %d\n", iv, jv );
          for ( i = 2; i <= val; ++i )
          {
              iv = iv;
              jv = jv-1;
              gasit = false;
              //fprintf( fout, "%d %d\n", iv, jv );
              BS( iv, jv );
              if ( gasit == true )
              {
                   nrsol++;
                   //fprintf( fout, "%d %d\n", iv, jv );
               }
          }
          ip = iv;
          jp = jv;
     }
     if ( c == 'E' ) 
     {
          iv = ip+1;
          jv = jp;
          gasit = false;
          BS( iv, jv );
          if ( gasit == true )
          {
               nrsol++;
               //fprintf( fout, "%d %d\n", iv, jv );
          }
          
//          fprintf( fout, "%d %d\n", iv, jv );
          for ( i = 2; i <= val; ++i )
          {
              iv = iv+1;
              jv = jv;
              gasit = false;
//              fprintf( fout, "%d %d\n", iv, jv );
              BS( iv, jv );
              if ( gasit == true )
              {
                   nrsol++;
                   //fprintf( fout, "%d %d\n", iv, jv );
               }
          }
          ip = iv;
          jp = jv;
     }
     if ( c == 'V' ) 
     {
          iv = ip-1;
          jv = jp;
          gasit = false;
          //fprintf( fout, "%d %d\n", iv, jv );
          BS( iv, jv );
          if ( gasit == true )
          {
               nrsol++;
               //fprintf( fout, "%d %d\n", iv, jv );
          }
          
          for ( i = 2; i <= val; ++i )
          {
              iv = iv-1;
              jv = jv;
              gasit = false;
              //fprintf( fout, "%d %d\n", iv, jv );
              BS( iv, jv );
              if ( gasit == true )
              {
                   nrsol++;
                   //fprintf( fout, "%d %d\n", iv, jv );
               }              
          }
          ip = iv;
          jp = jv;
     }
}

void BS( int x, int y )
{
     int bm, bl = 1, br = ind;
     while ( bl <= br )
     {
           bm = (bl+br)>>1;
           if ( a[bm].x > x ) br = bm - 1;
           else
           {
               if ( a[bm].x < x ) bl = bm + 1;
               else if ( a[bm].x == x )
               {
                    if ( a[bm].y > y ) br = bm - 1;
                    else if ( a[bm].y < y ) bl = bm + 1;
                    else if ( a[bm].y == y ) gasit = true, bl = br + 1;
               }
           }
     }
}