Cod sursa(job #2054445)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 1 noiembrie 2017 23:11:20
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 kb
#include <fstream>
#include <algorithm>
#define ff first
#define ss second
#define DIM 1300005
#define INF 2000000000

using namespace std;

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

int n, m, x, y, xi, yi, stanga, dreapta, stangaFin, dreaptaFin, xc, yc, cnt, val, sol, cntx, cnty;

char d;

pair<int, int> capcx[DIM], capcy[DIM];

int dx[] = {0, 0, 1, -1, 0, 0, 1, 1, -1, -1, 2, -2, 0, 0};
int dy[] = {0, 0, 0, 0, 1, -1, 1, -1, 1, -1, 0, 0, 2, -2};

#include <stdio.h>
#include <ctype.h>

class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

int main()
{
    InParser fin("zc.in");
    f>>n>>m;
    for(int i = 1; i <= n; ++ i){
        f>>x>>y;
        for(int ii = 1; ii <= 13; ++ ii){
            xc = x + dx[ii];
            yc = y + dy[ii];
            if(xc || yc){
                capcx[++cnt] = make_pair(xc, yc);
                capcy[cnt] = make_pair(yc, xc);
            }
        }
    }

    sort(capcx + 1, capcx + cnt + 1);


    for(int i = 2; i <= cnt; ++ i){
        if(capcx[i] != capcx[i - 1])
            capcx[++cntx] = capcx[i];

    }
    cnt = cntx;
    capcx[++cnt] = make_pair(INF, INF);
    for(int i = 1; i <= cnt; ++ i)
        capcy[i] = make_pair(capcx[i].ss, capcy[i].ff);
    sort(capcy + 1, capcy + cnt + 1);

    x = 0;
    y = 0;
    for(int i = 1; i <= m; ++ i){
        f>>d>>val;
        xi = x;
        yi = y;
        switch(d){
            case 'N': sol += (int)(upper_bound(capcx + 1, capcx + cnt + 1, make_pair(x, y + val)) - lower_bound(capcx + 1, capcx + cnt + 1, make_pair(x, y + 1))); y += val;break;
            case 'S': sol += (int)(upper_bound(capcx + 1, capcx + cnt + 1, make_pair(x, y - 1)) - lower_bound(capcx + 1, capcx + cnt + 1, make_pair(x, y - val))); y -= val;break;
            case 'V': sol += (int)(upper_bound(capcy + 1, capcy + cnt + 1, make_pair(y, x - 1)) - lower_bound(capcy + 1, capcy + cnt + 1, make_pair(y, x - val))); x -= val;break;
            case 'E': sol += (int)(upper_bound(capcy + 1, capcy + cnt + 1, make_pair(y, x + val)) - lower_bound(capcy + 1, capcy + cnt + 1, make_pair(y, x + 1))); x += val;break;
        }
    }

    g<<sol;

    return 0;
}