Cod sursa(job #1919335)

Utilizator hrazvanHarsan Razvan hrazvan Data 9 martie 2017 18:54:47
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <cstdio>
#include <algorithm>
#define MAXC 1300000
#define fs first
#define sc second
int d, nd;
std::pair<int, int> vx[MAXC], vy[MAXC];

inline void add(std::pair<int,int> *v, int x, int y){
  v[d].fs = x;
  v[d].sc = y;
}

inline int myabs(int x){
  return x < 0 ? -x : x;
}

bool cmp(std::pair<int,int> x, std::pair<int,int> y){
  if(x.fs < y.fs)
    return 1;
  if(x.fs > y.fs)
    return 0;
  if(x.sc < y.sc)
    return 1;
  return 0;
}

inline void elim(std::pair<int,int> *v){
  int j = 0, i;
  for(i = 1; i < d; i++){
    if(cmp(v[i - 1], v[i]) == 1)
      j++;
    v[j] = v[i];
  }
  nd = j + 1;
}

inline int caut(std::pair<int,int> *v, std::pair<int,int> p){
  int i = -1, pas;
  for(pas = (1 << 20); pas > 0; pas >>= 1)
    if(i + pas < d && cmp(v[i + pas], p) == 1)
      i += pas;
  return i + 1;
}

int main(){
  FILE *in = fopen("zc.in", "r");
  int n, m, i, a, b, da, db, ada, ad, x;
  long long rez = 0;
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < n; i++){
    fscanf(in, "%d%d ", &a, &b);
    for(da = -2; da <= 2; da++){
      ada = myabs(da);
      for(db = ada - 2; db <= 2 - ada; db++){
        add(vx, a + da, b + db);
        add(vy, b + db, a + da);
        d++;
      }
    }
  }
  std::sort(vx, vx + d);
  std::sort(vy, vy + d);
  elim(vx);
  elim(vy);
  d = nd;
  a = 0;  b = 0;
  char ch;
  std::pair<int,int> aux;
  for(i = 0; i < m; i++){
    ch = fgetc(in);
    fscanf(in, "%d ", &x);
    if(ch == 'E' || ch == 'V'){
      if(ch == 'E')
        aux.sc = a + x + 1;
      else
        aux.sc = a - x;
      aux.fs = b;
      ad = caut(vy, aux);
      if(ch == 'E'){
        aux.sc = a + 1;
        a += x;
      }
      else{
        aux.sc = a;
        a -= x;
      }
      ad -= caut(vy, aux);
      ad = myabs(ad);
      rez += ad;
    }
    else{
      if(ch == 'N')
        aux.sc = b + x + 1;
      else
        aux.sc = b - x;
      aux.fs = a;
      ad = caut(vx, aux);
      if(ch == 'N'){
        aux.sc = b + 1;
        b += x;
      }
      else{
        aux.sc = b;
        b -= x;
      }
      ad -= caut(vx, aux);
      ad = myabs(ad);
      rez += ad;
    }
  }
  FILE *out = fopen("zc.out", "w");
  fprintf(out, "%lld\n", rez);
  fclose(out);
  return 0;
}