Cod sursa(job #44030)

Utilizator cos_minBondane Cosmin cos_min Data 30 martie 2007 19:58:33
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.44 kb
#include <stdio.h>
#include <map>
#include <algorithm>
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 _px[13*dim], _py[13*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 Qsorty(int,int);
void Qsortx(int,int);
int BinaryS(int,int);
int BinarySx(int,int,int,int);
int BinarySy(int i, int j, int inou, int jnou);
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];
             _py[t] = py[t];
             _px[t] = px[t];
         }
     }
     
     N = t;
     
     for ( int i = 1; i <= M; i++ )
     {
         scanf("\n%c%d", &ac[i], &a[i] );
     }
}

void Solve()
{
     Qsortx(1,N);
     Qsorty(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;
     int inou, jnou;
     long long total = 0;
     
     ivec = jvec = 0;
     
     for ( int i = 1; i <= M; i++ )
     {
        inou = ivec + px1[ac[i]]*a[i];
        jnou = jvec + py1[ac[i]]*a[i];
        
        if ( ac[i] == 'N' || ac[i] == 'S' ) total += BinarySx(ivec,jvec,inou,jnou);
        else if ( ac[i] == 'E' || ac[i] == 'V' ) total += BinarySy(ivec,jvec,inou,jnou);
        ivec = inou;
        jvec = jnou;
     }
     
     printf("%lld", total);
}

int BinarySx(int i, int j, int inou, int jnou)
{
    
    int st = 1;
    int dr = N;
    int mij;
    int pozst, pozdr;
    int t = 0;
    
    if ( i < inou )
    {
       int ok = 0;
       // caut primul element >= i
       while ( st <= dr && ok == 0 )
       {
             mij = (st+dr)>>1;
             if ( px[mij] < i ) st = mij+1;
             else if ( px[mij] > i )
             {
                  dr = mij-1;
             }  
             else if ( px[mij] == i ) ok = 1, st = dr + 1, pozst = mij;
       }
       
       while ( px[mij-1] == px[mij] ) mij--;
       if ( ok == 0 ) pozst = mij;
       
       while ( px[pozst] <= inou )
       {
             if ( py[pozst] == j ) t += 1;
             pozst++; 
       }
    }
    else if ( inou < i )
    {
         int ok = 0;
       // caut primul element <= i
         while ( st <= dr && ok == 0 )
         {
             mij = (st+dr)>>1;
             if ( px[mij] < i ) st = mij+1;
             else if ( px[mij] > i )
             {
                  dr = mij-1;
             }  
             else if ( px[mij] == i ) ok = 1, st = dr + 1, pozst = mij;
         }
       
         while ( px[mij-1] == px[mij] ) mij--;
         if ( ok == 0 ) pozst = mij;
         
         while ( px[pozst] >= i )
         {
             if ( py[pozst] == j ) t += 1;
             pozst++; 
         }
    }

    return t;
}

void Qsortx(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 ) Qsortx(st,j);
     if ( i < dr ) Qsortx(i,dr);
}

void Qsorty(int st, int dr)
{
     int i = st-1;
     int j = dr+1;
     int pivot1 = _py[st];
     int pivot2 = _px[st];
     
     while ( i <= j )
     {
           do { i++; } while ( _py[i] < pivot1 || ( pivot1 == _py[i] && _px[i] < pivot2 ) );
           do { j--; } while ( _py[j] > pivot1 || ( pivot1 == _py[j] && _px[j] > pivot2 ) );
           
           if ( i <= j )
           {
                int aux = _py[i];
                _py[i] = _py[j];
                _py[j] = aux;
                int aux2 = _px[i];
                _px[i] = _px[j];
                _px[j] = aux2;
           }
     }
     
     if ( st < j ) Qsorty(st,j);
     if ( i < dr ) Qsorty(i,dr);
}

int BinarySy(int i, int j, int inou, int jnou)
{
    int st = 1;
    int dr = N;
    int mij;
    int pozst, pozdr;
    int t = 0;
    
    if ( j < jnou )
    {
       int ok = 0;
       // caut primul element >= j
       while ( st <= dr && ok == 0 )
       {
             mij = (st+dr)>>1;
             if ( _py[mij] < j ) st = mij+1;
             else if ( _py[mij] > j )
             {
                  dr = mij-1;
             }  
             else if ( _py[mij] == j ) ok = 1, st = dr + 1, pozst = mij;
       }
       
       while ( _py[mij-1] == _py[mij] ) mij--;
       if ( ok == 0 ) pozst = mij;
      // printf("%d ", pozst);
       
       while ( _py[pozst] <= jnou )
       {
             if ( _px[pozst] == i ) t += 1;
             pozst++; 
       }
       
      // printf("%d\n", pozst);
    }
    else if ( jnou < j )
    {
         int ok = 0;
       // caut primul element <= j
         while ( st <= dr && ok == 0 )
         {
             mij = (st+dr)>>1;
             if ( _py[mij] < j ) st = mij+1;
             else if ( _py[mij] > j )
             {
                  dr = mij-1;
             }  
             else if ( _py[mij] == j ) ok = 1, st = dr + 1, pozst = mij;
         }
       
         while ( _py[mij-1] == _py[mij] ) mij--;
         if ( ok == 0 ) pozst = mij;
         
         while ( _py[pozst] >= j )
         {
             if ( _px[pozst] == i ) t += 1;
             pozst++; 
         }
    }

    return t;
}