Cod sursa(job #2142104)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 24 februarie 2018 18:53:38
Problema Zota & Chidil Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>
using namespace std;

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

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

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

int main() {

	int n, m; in >> n >> m;

	vector< pair< int, int > >capcane;
	for(int i = 1; i <= n; ++i) {
		int x, y; in >> x >> y;

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

	sort(capcane.begin(),capcane.end(), cmpSort);

	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;
		if(direction == 'N') {
			nx = 0;
			ny = 1;
		} else {
			if(direction == 'E') {
				nx = 1;
				ny = 0;
			} else {
				if(direction == 'S') {
					nx = 0;
					ny = -1;
				} else {
					nx = -1;
					ny = 0;
				}
			}
		}

		while(steps) {
			currentPosition.first += nx;
			currentPosition.second += ny;
			
			if(binary_search(capcane.begin(), capcane.end(), currentPosition, cmpSearch))
				++ans;

			steps--;
		}
	}

	out << ans;

	in.close(); out.close();

	return 0;
}