Cod sursa(job #2142317)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 24 februarie 2018 22:10:31
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.81 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream in("zc.in");
ofstream out("zc.out");
 
int cmpXSort(const pair< int, int > &a, const pair< int, int > &b) {
    if(a.first == b.first)
        return a.second < b.second;
    else
        return a.first < b.first;
}

int cmpYSort(const pair< int, int > &a, const pair< int, int > &b) {
	if(a.second == b.second)
        return a.first < b.first;
    else
        return a.second < b.second;
}

bool cmpXSearch(const pair< int, int > &a, const pair< int, int > &b) {
    if(a.first == b.first)
        return (a.second < b.second);
    else
        return (a.first < b.first);
}

bool cmpYSearch(const pair< int, int > &a, const pair< int, int > &b) {
    if(a.second == b.second)
        return (a.first < b.first);
    else
        return (a.second < b.second);
}
 
int main() {
 
    int n, m; in >> n >> m;
 
    vector< pair< int, int > > capcaneX;
    vector< pair< int, int > > capcaneY;
    for(int i = 1; i <= n; ++i) {
        int x, y; in >> x >> y;

        capcaneX.push_back(make_pair(x + 1, y));
        capcaneX.push_back(make_pair(x + 2, y));
        capcaneX.push_back(make_pair(x - 1, y));
        capcaneX.push_back(make_pair(x - 2, y));
        capcaneX.push_back(make_pair(x, y + 1));
        capcaneX.push_back(make_pair(x, y + 2));
        capcaneX.push_back(make_pair(x, y - 1));
        capcaneX.push_back(make_pair(x, y - 2));
        capcaneX.push_back(make_pair(x - 1, y + 1));
        capcaneX.push_back(make_pair(x + 1, y + 1));
        capcaneX.push_back(make_pair(x - 1, y - 1));
        capcaneX.push_back(make_pair(x + 1, y - 1));

        capcaneY.push_back(make_pair(x + 1, y));
        capcaneY.push_back(make_pair(x + 2, y));
        capcaneY.push_back(make_pair(x - 1, y));
        capcaneY.push_back(make_pair(x - 2, y));
        capcaneY.push_back(make_pair(x, y + 1));
        capcaneY.push_back(make_pair(x, y + 2));
        capcaneY.push_back(make_pair(x, y - 1));
        capcaneY.push_back(make_pair(x, y - 2));
        capcaneY.push_back(make_pair(x - 1, y + 1));
        capcaneY.push_back(make_pair(x + 1, y + 1));
        capcaneY.push_back(make_pair(x - 1, y - 1));
        capcaneY.push_back(make_pair(x + 1, y - 1));
    }
 
    sort(capcaneX.begin(),capcaneX.end(), cmpXSort);
    sort(capcaneY.begin(),capcaneY.end(), cmpYSort);

    pair< int, int > currentPosition = make_pair(0, 0);
    int ans = 0;
 
    for(int i = 1; i <= m; ++i) {
        char direction;
        int steps;
 
        in >> direction >> steps;
 
        int nx, ny;
        int dir;

        if(direction == 'N') {
            nx = 0;
            ny = 1;
            dir = 1;
        } else {
            if(direction == 'E') {
                nx = 1;
                ny = 0;
                dir = 2;
            } else {
                if(direction == 'S') {
                    nx = 0;
                    ny = -1;
                    dir = 1;
                } else {
                    nx = -1;
                    ny = 0;
                    dir = 2;
                }
            }
        }
 	
        pair< int, int > finalPosition = make_pair(currentPosition.first + steps * nx, currentPosition.second + steps * ny);

        if(dir == 2) {
        	int low = lower_bound(capcaneY.begin(), capcaneY.end(), currentPosition, cmpYSearch) - capcaneY.begin();
        	int upper = lower_bound(capcaneY.begin(), capcaneY.end(), finalPosition, cmpYSort) - capcaneY.begin();

        	ans += (upper - low);
        } else {
        	int low = lower_bound(capcaneX.begin(), capcaneX.end(), currentPosition, cmpXSearch) - capcaneX.begin();
        	int upper = lower_bound(capcaneX.begin(), capcaneX.end(), finalPosition, cmpXSort) - capcaneX.begin();

        	ans += (upper - low);
        }

        currentPosition = finalPosition;
    }
 
    out << ans << '\n';
 
    in.close(); out.close();
 
    return 0;
}