Cod sursa(job #81933)

Utilizator cos_minBondane Cosmin cos_min Data 5 septembrie 2007 13:11:09
Problema Zota & Chidil Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.9 kb
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <set>
using namespace std;

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

int N, M;
int X[13*dim], Y[13*dim];
int Ax[13*dim], Ay[13*dim], Bx[13*dim], By[13*dim];
int size1 = 1, size2 = 1;

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 Qsortx(int,int);
void Qsorty(int,int);
void BinarySx(int,int);
void BinarySy(int,int);

struct Functorx {
    bool operator () (int i, int j)
    {
         if ( X[i] == X[j] ) return Y[i] < Y[j];
         return X[i] < X[j];
    }
};

struct Functory {
    bool operator () (int i, int j)
    {
         if ( Y[i] == Y[j] ) return X[i] < X[j];
         return Y[i] < Y[j];
    }
};

set<int, Functorx> S;
set<int, Functorx>::iterator itx;
set<int, Functory> D;
set<int, Functory>::iterator ity;

int SolveX(int,int,int);
int SolveY(int,int,int);

int main()
{
    int x, y, q = 0;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d", &N, &M);
    for ( int i = 1; i <= N; i++ )
    {
        scanf("%d%d", &x, &y); 
        for ( int dir = 0; dir < 13; dir++ )
        {
            q++;
            X[q] = x+di[dir];
            Y[q] = y+dj[dir];
            
            S.insert(q); D.insert(q);
        }
    }
    
    
    itx = S.begin(), ity = D.begin();
    
    Ax[size1] = X[*itx], Ay[size1] = Y[*itx];
    Bx[size2] = X[*ity], By[size2] = Y[*ity];
    
    for ( ; itx != S.end(); ++itx, ++ity )
    {
        if ( Ax[size1] != X[*itx] || Ay[size2] != Y[*itx] ) size1++, Ax[size1] = X[*itx], Ay[size1] = Y[*itx];
        if ( Bx[size2] != X[*ity] || By[size2] != Y[*ity] ) size2++, Bx[size2] = X[*ity], By[size2] = Y[*ity];
    }
    
    char Ch;
    int T;
    
    int ivec, jvec, total=0;
    ivec = jvec = 0;
    
    /*for ( int i = 1; i <= size2; i++ )*
        printf("%d %d\n", Bx[i], By[i])*/
    
    for ( int i = 1; i <= M; i++ )
    {
        scanf("\n%c%d", &Ch, &T);

        if ( Ch == 'N' || Ch == 'S' ) 
        {
             if ( Ch == 'S' ) total += SolveY(ivec,jvec,jvec-T), jvec -= T;
             else             total += SolveY(ivec,jvec,jvec+T), jvec += T;
             
        }
        else
        {
            if ( Ch == 'E' ) total += SolveX(ivec,jvec,ivec+T), ivec += T;
            else             total += SolveX(ivec,jvec,ivec-T), ivec -= T;
        }
        
        //printf("%d\n", total);
    }
    
    printf("%d", total);   
}

int SolveY(int iv, int jv, int jnou)
{
    int st=1, dr=size1, mij, ok = 0, s = 0;
    
    while ( st <= dr )
    {
          mij = (st+dr)>>1;
          if ( Ax[mij] > iv ) dr = mij-1;
          else if ( Ax[mij] < iv ) st = mij+1;
          else ok = mij, dr = mij-1;
    }
    
    int minim = jv, maxim = jv;
    
    if ( minim > jnou ) minim = jnou;
    if ( maxim < jnou ) maxim = jnou;
    
    if ( ok == 0 ) return s;
    else
    {
        for ( int poz = ok; poz <= size1 && Ay[poz] <= maxim && Ax[poz] == iv; poz++ ) 
        {
            if ( Ay[poz] >= minim  && Ay[poz] <= maxim ) s += 1;
        }
        
        return s;
    } 
}

int SolveX(int iv, int jv, int inou)
{
    int st=1, dr=size2, mij, ok = 0, s = 0;
    
    while ( st <= dr )
    {
          mij = (st+dr)>>1;
          if ( By[mij] > jv ) dr = mij-1;
          else if ( By[mij] < jv ) st = mij+1;
          else ok = mij, dr = mij-1;
    }
    
    int minim = iv, maxim = iv;
    
    if ( minim > inou ) minim = inou;
    if ( maxim < inou ) maxim = inou;
    
    if ( ok == 0 ) return s;
    else
    {
        for ( int poz = ok; poz <= size2 && Bx[poz] <= maxim && By[poz] == jv; poz++ ) 
        {
            if ( Bx[poz] >= minim && Bx[poz] <= maxim ) s += 1;
        }
        
        return s;
    } 
}