Cod sursa(job #755474)

Utilizator GrimpowRadu Andrei Grimpow Data 5 iunie 2012 21:20:53
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const char iname[] = "zc.in";
const char oname[] = "zc.out";

#define PB push_back
#define MP make_pair

vector < pair <int, int> > trapsX, trapsY;


bool start_position(pair <int, int> &p) {
	return (p.first == 0) && (p.second == 0);
}

int main(void)
{
	int n;
	int m;
	int x, y;
	int steps;
	int res;
	char dir;

	FILE *fi = fopen(iname, "r");
	fscanf(fi, "%d\n", &n);
	fscanf(fi, "%d\n", &m);
	for (int cntr = 0; cntr < n; ++ cntr) {
		fscanf(fi, "%d %d\n", &x, &y);
		for (int j = -2; j <= 2; ++ j) {
			trapsX.PB(MP(x, y + j));
			trapsY.PB(MP(y + j, x));
		}
		for (int j = -1; j <= 1; ++ j) {
			trapsX.PB(MP(x - 1, y + j)), trapsX.PB(MP(x + 1, y + j));
			trapsY.PB(MP(y + j, x - 1)), trapsY.PB(MP(y + j, x + 1));
		}
		trapsX.PB(MP(x - 2, y)), trapsX.PB(MP(x + 2, y));
		trapsY.PB(MP(y, x - 2)), trapsY.PB(MP(y, x + 2));
	}
	vector < pair <int, int> >::iterator new_end = remove_if(trapsX.begin(), trapsX.end(), start_position);
	trapsX.erase(new_end, trapsX.end());
	new_end = remove_if(trapsY.begin(), trapsY.end(), start_position);
	trapsY.erase(new_end, trapsY.end());

	sort(trapsX.begin(), trapsX.end());
	vector < pair <int, int> >::iterator new_endX = unique(trapsX.begin(), trapsX.end());
	sort(trapsY.begin(), trapsY.end());
	vector < pair <int, int> >::iterator new_endY = unique(trapsY.begin(), trapsY.end());

	x = y = 0;
	res = 0;
	for (int cntr = 0; cntr < m; ++ cntr) {
		fscanf(fi, "%c %d\n", &dir, &steps);
		switch (dir) {
			case 'N': 
				res += upper_bound(trapsX.begin(), trapsX.end(), MP(x, y + steps)) -
					   upper_bound(trapsX.begin(), trapsX.end(), MP(x, y));
				y += steps;
				break ;
			case 'E':
				res += upper_bound(trapsY.begin(), trapsY.end(), MP(y, x + steps)) -
					   upper_bound(trapsY.begin(), trapsY.end(), MP(y, x));
				x += steps;
				break ;
			case 'S':
				res += upper_bound(trapsX.begin(), trapsX.end(), MP(x, y - 1)) -
					   upper_bound(trapsX.begin(), trapsX.end(), MP(x, y - steps - 1));
				y -= steps;
				break ;
			case 'V':
				res += upper_bound(trapsY.begin(), trapsY.end(), MP(y, x - 1)) -
					   upper_bound(trapsY.begin(), trapsY.end(), MP(y, x - steps - 1));
				x -= steps;
				break ;
		}
	}	
	fclose(fi);

	FILE *fo = fopen(oname, "w");

	fprintf(fo, "%d", res);
	fclose(fo);

	return 0;
}