Cod sursa(job #1263043)

Utilizator diana97Diana Ghinea diana97 Data 13 noiembrie 2014 20:55:50
Problema Zota & Chidil Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define mp make_pair

using namespace std;

ifstream f ("zc.in");
ofstream g ("zc.out");

const int NMAX = 100000 + 1;

int n, m;
vector < pair <int, int> > capcane, capcane2;
    int v[100];

bool inside(int x, int y) {
    if (x < 0 || y < 0) return false;
    return true;
}

inline int modul(int x) {
    if (x > 0) return x;
    return -x;
}

void citeste() {
    f >> n >> m;
    int a, b;
    for (int i = 1; i <= n; i++) {
        f >> a >> b;
        for (int dx = -2; dx <= 2; dx++)
            for (int dy = -2; dy <= 2; dy++)
                if ((a + dx || b + dy) && (modul(dx) + modul(dy) <= 2)) {
                    capcane.push_back(make_pair(a + dx, b + dy));
                }
    }
}

int cauta_stanga(pair <int, int> loc, vector < pair <int, int> > capcane) {
    int sol = 0, st = 0, dr = capcane.size() - 1, m;
    while (st <= dr) {
        m = (st + dr) / 2;
        if (capcane[m] <= loc) {sol = m + 1; st = m + 1;}
        else {dr = m - 1;}
    }
    return sol;
}

int cauta_dreapta(pair <int, int> loc, vector < pair <int, int> > capcane) {
    int sol = -1, st = 0, dr = capcane.size() - 1, m;
    while (st <= dr) {
        m = (st + dr) / 2;
        if (capcane[m] == loc) dr = m -  1;
        else if (capcane[m] >= loc) {sol = m; dr = m - 1;}
        else {st = m + 1;}
    }
    if (sol == -1) return capcane.size();
    return sol;
}

void rezolva() {
    sort(capcane.begin(), capcane.end());
    capcane.resize(unique(capcane.begin() , capcane.end()) - capcane.begin());
    n = 0;
    for (int i = 1; i < capcane.size(); i++)
        if (capcane[i] != capcane[i - 1])
            capcane[++n] = capcane[i];
    capcane.resize(n + 1);
    for (int i = 0; i < capcane.size(); i++) capcane2.push_back(make_pair(capcane[i].second, capcane[i].first));
    sort (capcane2.begin(), capcane2.end());

    int X = 0, Y = 0, sol = 0;
    char c; int d;
    while (m--) {
        f >> c >> d;
        if (c == 'N') {
            sol += cauta_dreapta(make_pair(X, Y + d), capcane) - cauta_stanga(make_pair(X, Y + 1), capcane);
            Y += d;
        }
        else if (c == 'S') {
            sol += cauta_dreapta(make_pair(X, Y - 1), capcane) - cauta_stanga(make_pair(X, Y - d), capcane);
            Y -= d;
        }
        else if (c == 'E') {
            sol += cauta_dreapta(make_pair(Y, X + d), capcane2) - cauta_stanga(make_pair(Y, X + 1), capcane2);
            X += d;
        }
        else {
            sol += cauta_dreapta(make_pair(Y, X - 1), capcane2) - cauta_stanga(make_pair(Y, X - d), capcane2);
            X -= d;
        }
    }
    g << sol << '\n';
}

int main() {
    citeste();
    rezolva();
    return 0;
}