Cod sursa(job #959219)

Utilizator primulDarie Sergiu primul Data 8 iunie 2013 10:36:03
Problema Zota & Chidil Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <cstdio>
#include <vector>
#include <algorithm>
  
using namespace std;
  
const char iname[] = "zc.in";
const char oname[] = "zc.out";
  
#define PB push_back
#define MP make_pair
  
vector < pair <int, int> > trapsX, trapsY;
  
  
bool start_position(pair <int, int> &p) {
    return (p.first == 0) && (p.second == 0);
}
  
int main(void)
{
    int n;
    int m;
    int x, y;
    int steps;
    int res;
    char dir;
  
    FILE *fi = fopen(iname, "r");
    /* trapsX */
    fscanf(fi, "%d\n", &n);
    fscanf(fi, "%d\n", &m);
    for (int cntr = 0; cntr < n; ++ cntr) {
        fscanf(fi, "%d %d\n", &x, &y);
        for (int j = -2; j <= 2; ++ j) {
            trapsX.PB(MP(x, y + j));
            trapsY.PB(MP(y + j, x));
        }
        for (int j = -1; j <= 1; ++ j) {
            trapsX.PB(MP(x - 1, y + j)), trapsX.PB(MP(x + 1, y + j));
            trapsY.PB(MP(y + j, x - 1)), trapsY.PB(MP(y + j, x + 1));
        }
        trapsX.PB(MP(x - 2, y)), trapsX.PB(MP(x + 2, y));
        trapsY.PB(MP(y, x - 2)), trapsY.PB(MP(y, x + 2));
    }
    vector < pair <int, int> >::iterator new_end = remove_if(trapsX.begin(), trapsX.end(), start_position);
    trapsX.erase(new_end, trapsX.end());
    new_end = remove_if(trapsY.begin(), trapsY.end(), start_position);
    trapsY.erase(new_end, trapsY.end());
  
    sort(trapsX.begin(), trapsX.end());
    vector < pair <int, int> >::iterator new_endX = unique(trapsX.begin(), trapsX.end());
    sort(trapsY.begin(), trapsY.end());
    vector < pair <int, int> >::iterator new_endY = unique(trapsY.begin(), trapsY.end());
  
    x = y = 0;
    res = 0;
    for (int cntr = 0; cntr < m; ++ cntr) {
        fscanf(fi, "%c %d\n", &dir, &steps);
        switch (dir) {
            case 'N':
                res += upper_bound(trapsX.begin(), trapsX.end(), MP(x, y + steps)) -
                       upper_bound(trapsX.begin(), trapsX.end(), MP(x, y));
                y += steps;
                break ;
            case 'E':
                res += upper_bound(trapsY.begin(), trapsY.end(), MP(y, x + steps)) -
                       upper_bound(trapsY.begin(), trapsY.end(), MP(y, x));
                x += steps;
                break ;
            case 'S':
                res += upper_bound(trapsX.begin(), trapsX.end(), MP(x, y - 1)) -
                       upper_bound(trapsX.begin(), trapsX.end(), MP(x, y - steps - 1));
                y -= steps;
                break ;
            case 'V':
                res += upper_bound(trapsY.begin(), trapsY.end(), MP(y, x - 1)) -
                       upper_bound(trapsY.begin(), trapsY.end(), MP(y, x - steps - 1));
                x -= steps;
                break ;
        }
    } 
    fclose(fi);
  
    FILE *fo = fopen(oname, "w");
  
    fprintf(fo, "%d", res);
    fclose(fo);
  
    return 0;
}