Cod sursa(job #1510099)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 octombrie 2015 16:09:04
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

constexpr bool x_sort(const pair<int, int> a, const pair<int, int> b){
	return a.first < b.first || (a.first == b.first && a.second < b.second); }

constexpr bool y_sort(const pair<int, int> a, const pair<int, int> b){
	return a.second < b.second || (a.second == b.second && a.first < b.first); }

constexpr pair<int, int> dists[] =
	{ {-2, 0}, {-1, -1}, {-1, 0}, {-1, 1}, {0, -2}, {0, -1}, {0, 0}, {0, 1}, {0, 2}, {1, -1}, {1, 0}, {1, 1}, {2, 0} };

void add_all_points(const pair<int, int>& p, vector<pair<int, int> >& vx, vector<pair<int, int> >& vy){
	int x, y;
	for(const auto d : dists){
		x = p.first + d.first;
		y = p.second + d.second;
		if(x != 0 || y != 0){
			vx.emplace_back(x, y);
			vy.emplace_back(x, y); } } }

int nr_affected(pair<int, int>& poz_cur, const char dir, const int l, const vector<pair<int, int> >& vx,
	const vector<pair<int, int> >& vy){
	pair<int, int> dest;
	int rez = 0;
	if(dir == 'N'){
		dest = {poz_cur.first, poz_cur.second + l};
		rez = upper_bound(begin(vx), end(vx), dest, x_sort) - lower_bound(begin(vx), end(vx), poz_cur, x_sort); }
	else if(dir == 'S'){
		dest = {poz_cur.first, poz_cur.second - l};
		rez = upper_bound(begin(vx), end(vx), poz_cur, x_sort) - lower_bound(begin(vx), end(vx), dest, x_sort); }
	else if(dir == 'E'){
		dest = {poz_cur.first + l, poz_cur.second};
		rez = upper_bound(begin(vy), end(vy), dest, y_sort) - lower_bound(begin(vy), end(vy), poz_cur, y_sort); }
	else{
		dest = {poz_cur.first - l, poz_cur.second};
		rez = upper_bound(begin(vy), end(vy), poz_cur, y_sort) - lower_bound(begin(vy), end(vy), poz_cur, y_sort); }
	
	poz_cur = dest;
	return rez; }

int main(){
	ifstream f("zc.in");
	ofstream g("zc.out");
	int n, m;
	f >> n >> m;
	vector<pair<int, int> > vx, vy;
	for(int i = 0, x, y; i < n; ++i){
		f >> x >> y;
		add_all_points({x, y}, vx, vy); }

	sort(begin(vx), end(vx), x_sort);
	vx.erase(unique(begin(vx), end(vx)), end(vx));

	sort(begin(vy), end(vy), y_sort);
	vy.erase(unique(begin(vy), end(vy)), end(vy));

	int rez = 0;
	pair<int, int> poz_cur = {0, 0};
	char dir;
	for(int i = 0, l; i < m; ++i){
		f >> dir >> l;
		rez += nr_affected(poz_cur, dir, l, vx, vy); }
	g << rez;
	return 0; }