Cod sursa(job #1919286)

Utilizator hrazvanHarsan Razvan hrazvan Data 9 martie 2017 18:37:40
Problema Zota & Chidil Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <cstdio>
#include <algorithm>
#define MAXC 1300000
typedef struct{
  int x, y;
}pnt;
int d, nd;
pnt vx[MAXC], vy[MAXC];

inline void add(pnt *v, int x, int y){
  v[d].x = x;
  v[d].y = y;
}

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

bool cmp(pnt x, pnt y){
  if(x.x < y.x)
    return 1;
  if(x.x > y.x)
    return 0;
  if(x.y < y.y)
    return 1;
  return 0;
}

inline void elim(pnt *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(pnt *v, pnt p){
  int i = -1, pas;
  for(pas = (1 << 19); 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, x, ad;
  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, cmp);
  std::sort(vy, vy + d, cmp);
  elim(vx);
  elim(vy);
  d = nd;
  a = 0;  b = 0;
  char ch;
  pnt aux;
  for(i = 0; i < m; i++){
    ch = fgetc(in);
    fscanf(in, "%d ", &x);
    if(ch == 'E' || ch == 'V'){
      if(ch == 'E')
        aux.y = a + x + 1;
      else
        aux.y = a - x;
      aux.x = b;
      ad = caut(vy, aux);
      if(ch == 'E'){
        aux.y = a + 1;
        a += x;
      }
      else{
        aux.y = a;
        a -= x;
      }
      ad -= caut(vy, aux);
      ad = myabs(ad);
      rez += ad;
    }
    else{
      if(ch == 'N')
        aux.y = b + x + 1;
      else
        aux.y = b - x;
      aux.x = a;
      ad = caut(vx, aux);
      if(ch == 'N'){
        aux.y = b + 1;
        b += x;
      }
      else{
        aux.y = b + 1;
        b -= x;
      }
      ad -= caut(vx, aux);
      ad = myabs(ad);
      rez += ad;
    }
  }
  FILE *out = fopen("zc.out", "w");
  fprintf(out, "%lld", rez);
  fclose(out);
  return 0;
}