Cod sursa(job #168509)

Utilizator scvalexAlexandru Scvortov scvalex Data 31 martie 2008 16:01:29
Problema Zota & Chidil Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

const int dirs[13][2] = {
	{0, 0},
	{-1, 0},
	{-2, 0},
	{1, 0},
	{2, 0},

	{0, -1},
	{0, -2},
	{0, 1},
	{0, 2},
	{-1, -1},

	{-1, 1},
	{1, -1},
	{1, 1},
};

vector<pii> vx,
	vy;

bool ltx(const pii &a, const pii &b) {
	if (a.first == b.first)
		return a.second < b.second;
	return a.first < b.first;
}

bool lty(const pii &a, const pii &b) {
	if (a.second == b.second)
		return a.first < b.first;
	return a.second < b.second;
}
int main(int argc, char *argv[]) {
	FILE *fi = fopen("zc.in", "r");
	int N, M;
	fscanf(fi, "%d %d", &N, &M);
	int x, y;
	for (int i(0); i < N; ++i) {
		fscanf(fi, "%d %d\n", &x, &y);
		for (int d(0); d < 13; ++d)
			if ((x + dirs[d][0] != 0) || (y + dirs[d][1] != 0))
				vx.push_back(make_pair(x + dirs[d][0], y + dirs[d][1]));
	}
	vy = vx;
	sort(vx.begin(), vx.end(), ltx);
	sort(vy.begin(), vy.end(), lty);

	vx.erase(unique(vx.begin(), vx.end()), vx.end());
	vy.erase(unique(vy.begin(), vy.end()), vy.end());

	/*for (int i(0); i < (int)vx.size(); ++i)
		cout << i << "\t:\t" << vx[i].first << " " << vx[i].second << "\t|\t" << vy[i].first << " " << vy[i].second << endl;*/

	char c;
	int d;
	x = y = 0;
	int nx = 0,
		ny = 0;
	int tot = 0;
	for (int i(0); i < M; ++i) {
		fscanf(fi, "%c %d\n", &c, &d);
		//cout << c << " " << d << endl;
		if (c == 'N')
			ny += d;
		else if (c == 'S')
			ny -= d;
		else if (c == 'V')
			nx -= d;
		else 
			nx += d;

		//cout << nx << " " << ny << endl;
		if ((c == 'N') || (c == 'S')) {
			/*cout << upper_bound(vx.begin(), vx.end(), make_pair(nx, ny), ltx) -
				lower_bound(vx.begin(), vx.end(), make_pair(nx, y), ltx) << endl;*/
			tot += upper_bound(vx.begin(), vx.end(), make_pair(nx, ny), ltx) -
				lower_bound(vx.begin(), vx.end(), make_pair(nx, y), ltx);
		} else if ((c == 'V') || (c == 'E')) {
			/*cout << upper_bound(vy.begin(), vy.end(), make_pair(nx, ny), lty) -
				lower_bound(vy.begin(), vy.end(), make_pair(x, ny), lty) << endl;*/
			tot += upper_bound(vy.begin(), vy.end(), make_pair(nx, ny), lty) -
				lower_bound(vy.begin(), vy.end(), make_pair(x, ny), lty);
		}
		
		x = nx;
		y = ny;
	}
	fclose(fi);

	ofstream fout("zc.out");
	fout << tot << endl;
	fout.close();

	return 0;
}