Cod sursa(job #5658)

Utilizator zombie_testeala bala portocala si mandarina zombie_teste Data 13 ianuarie 2007 17:23:18
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define PB push_back
#define MP make_pair

const int ND = 13;
const int tx[] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
const int ty[] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};

int N, M;
vector <pair <int, int> > X, Y;

void nosame(vector <pair <int, int> > *Z) {
	int k, i, stop = (int) (*Z).size();
	
	for (k = 0, i = 1; i < stop; ++i)
		if ((*Z)[i - 1] == (*Z)[i])
			++k;
		else
			(*Z)[i - k] = (*Z)[i];
	
	for (i = 0; i < k; ++i) (*Z).pop_back();
}

void afis(vector <pair <int, int> > *Z) {
	unsigned i;
	for (i = 0; i < (*Z).size(); ++i)
		printf("(%d, %d) ", (*Z)[i].first, (*Z)[i].second);
	printf("\n\n");
}

int main() {	
	FILE *fin = fopen("zc.in", "rt");
	FILE *fout = fopen("zc.out", "wt");
	int i, j, x, y, x1, y1, pas;
	char dir;
	long long rez = 0;
	vector <pair <int, int> > :: iterator it1, it2;

	fscanf(fin, " %d %d", &N, &M);

	X.reserve(N * ND);
	Y.reserve(N * ND);

	for (i = 0; i < N; ++i) {
		fscanf(fin, " %d %d", &x, &y);
		
		for (j = 0; j < ND; ++j) {
			x1 = x + tx[j]; y1 = y + ty[j];
			if (x1 != 0 || y1 != 0)
				X.PB(MP(x1, y1)),
				Y.PB(MP(y1, x1));
		}
	}

//	afis(&X);
//	afis(&Y);

	sort(X.begin(), X.end());
	sort(Y.begin(), Y.end());
	
//	afis(&X);
//	afis(&Y);
	
	nosame(&X);
	nosame(&Y);

	x = 0; y = 0;
	
//	afis(&X);
//	afis(&Y);

	for (i = 0; i < M; ++i) {
		fscanf(fin, " %c %d", &dir, &pas);
		switch (dir) {
			case 'S': 
				x1 = x; y1 = y - pas;
				it1 = lower_bound(X.begin(), X.end(), MP(x1, y1));
				it2 = lower_bound(X.begin(), X.end(), MP(x, y));
				break;
			case 'N':
				x1 = x; y1 = y + pas;
				it1 = upper_bound(X.begin(), X.end(), MP(x, y));
				it2 = upper_bound(X.begin(), X.end(), MP(x1, y1));
				break;
			case 'V':
				x1 = x - pas; y1 = y;
				it1 = lower_bound(Y.begin(), Y.end(), MP(y1, x1));
				it2 = lower_bound(Y.begin(), Y.end(), MP(y, x));
				break;
			case 'E':
				x1 = x + pas; y1 = y;
				it1 = upper_bound(Y.begin(), Y.end(), MP(y, x));
				it2 = upper_bound(Y.begin(), Y.end(), MP(y1, x1));
				break;
			default:
				x1 = x; y1 = y;
				it1 = X.begin(); it2 = X.begin();
				break;
		}

		rez += it2 - it1;
//		printf("pas %d : (%d, %d) -> (%d, %d)\n", i, x, y, x1, y1);
//		printf("found : (%d, %d) -> (%d, %d)\n\n",(*it1).first, (*it1).second, (*it2).first, (*it2).second);
		x = x1; y = y1;
	}

	fprintf(fout, "%lld\n", rez);

	fclose(fin);
	fclose(fout);

	return 0;
}