Cod sursa(job #915219)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 14 martie 2013 20:16:30
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.04 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));
        }
    }
 
//  afis(&X);
//  afis(&Y);
 
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
     
//  afis(&X);
//  afis(&Y);
     
    nosame(&X);
    nosame(&Y);
 
    x = 0; y = 0;
     
//  afis(&X);
//  afis(&Y);
 
    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;
//      printf("pas %d : (%d, %d) -> (%d, %d)\n", i, x, y, x1, y1);
//      printf("found : (%d, %d) -> (%d, %d)\n\n",(*it1).first, (*it1).second, (*it2).first, (*it2).second);
        x = x1; y = y1;
    }
 
    fprintf(fout, "%lld\n", rez);
 
    fclose(fin);
    fclose(fout);
 
    return 0;
}