Cod sursa(job #990572)

Utilizator otto1Palaga Vicentiu-Octavian otto1 Data 28 august 2013 17:39:27
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define PB push_back
#define MP make_pair

const int ND = 13;
const int tx[] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
const int ty[] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};

int N, M;
vector <pair <int, int> > X, Y;

void nosame(vector <pair <int, int> > *Z) {
    int k, i, stop = (int) (*Z).size();

    for (k = 0, i = 1; i < stop; ++i)
        if ((*Z)[i - 1] == (*Z)[i])
            ++k;
        else
            (*Z)[i - k] = (*Z)[i];

    for (i = 0; i < k; ++i) (*Z).pop_back();
}

void afis(vector <pair <int, int> > *Z) {
    unsigned i;
    for (i = 0; i < (*Z).size(); ++i)
        printf("(%d, %d) ", (*Z)[i].first, (*Z)[i].second);
    printf("\n\n");
}

int main() {
    FILE *fin = fopen("zc.in", "rt");
    FILE *fout = fopen("zc.out", "wt");
    int i, j, x, y, x1, y1, pas;
    char dir;
    long long rez = 0;
    vector <pair <int, int> > :: iterator it1, it2;

    fscanf(fin, " %d %d", &N, &M);

    X.reserve(N * ND);
    Y.reserve(N * ND);

    for (i = 0; i < N; ++i) {
        fscanf(fin, " %d %d", &x, &y);

        for (j = 0; j < ND; ++j) {
            x1 = x + tx[j]; y1 = y + ty[j];
            if (x1 != 0 || y1 != 0)
                X.PB(MP(x1, y1)),
                Y.PB(MP(y1, x1));
        }
    }



    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());



    nosame(&X);
    nosame(&Y);

    x = 0; y = 0;



    for (i = 0; i < M; ++i) {
        fscanf(fin, " %c %d", &dir, &pas);
        switch (dir) {
            case 'S':
                x1 = x; y1 = y - pas;
                it1 = lower_bound(X.begin(), X.end(), MP(x1, y1));
                it2 = lower_bound(X.begin(), X.end(), MP(x, y));
                break;
            case 'N':
                x1 = x; y1 = y + pas;
                it1 = upper_bound(X.begin(), X.end(), MP(x, y));
                it2 = upper_bound(X.begin(), X.end(), MP(x1, y1));
                break;
            case 'V':
                x1 = x - pas; y1 = y;
                it1 = lower_bound(Y.begin(), Y.end(), MP(y1, x1));
                it2 = lower_bound(Y.begin(), Y.end(), MP(y, x));
                break;
            case 'E':
                x1 = x + pas; y1 = y;
                it1 = upper_bound(Y.begin(), Y.end(), MP(y, x));
                it2 = upper_bound(Y.begin(), Y.end(), MP(y1, x1));
                break;
            default:
                x1 = x; y1 = y;
                it1 = X.begin(); it2 = X.begin();
                break;
        }

        rez += it2 - it1;
       x = x1; y = y1;
    }

    fprintf(fout, "%lld\n", rez);

    fclose(fin);
    fclose(fout);

    return 0;
}