Cod sursa(job #2882)

Utilizator wefgefAndrei Grigorean wefgef Data 19 decembrie 2006 18:54:03
Problema Zota & Chidil Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define x first
#define y second
#define mp(a, b) make_pair(a, b)
#define pb(v, a) v.push_back(a)
#define sz(a) a.size()

vector< pair<int, int> > v, u;
int m;
long long rez;

void readdata()
{
	freopen("zc.in", "r", stdin);
	freopen("zc.out", "w", stdout);
	
	int nr, i, j, pas, a, b, lim, cont = 1, n1 = 0, n2 = 0;
	
	scanf("%d %d", &nr, &m);
	for (pas = 0; pas < nr; ++pas)
	{
		scanf("%d %d", &a, &b);
		for (i = a-2; i <= a+2; ++i)
		for (j = b-2; j <= b+2; ++j)
			if (abs(i-a) + abs(j-b) <= 2)
			if (i || j)
			{
				pb(v, mp(i, j));
				pb(u, mp(j, i));
			}
	}
	sort(u.begin(), u.end());
	sort(v.begin(), v.end());
	lim = sz(v);
	if (lim == 0) return;
	for (i = 1; i < lim; ++i)
	{
		if (v[i] > v[i-1]) v[++n1] = v[i];
		if (u[i] > u[i-1])
		{
			u[++n2] = u[i];
			cont++;
		}
	}
	cont = sz(v)-cont;
	for (i = 0; i < cont; ++i)
	{
		v.pop_back();
		u.pop_back();
	}
}

int search1(pair<int, int> k)
{
	int st = 0, dr = sz(v)-1, m;
	
	while (st < dr)
	{
		m = (st+dr+1)/2;
		if (v[m] <= k) st = m;
		else dr = m-1;
	}
	if (dr > st) return -1;
	if (st == 0 && v[st] > k) return -1;
	return st;
}

int search2(pair<int, int> k)
{
	int st = 0, dr = sz(u)-1, m;
	
	while (st < dr)
	{
		m = (st+dr+1)/2;
		if (u[m] <= k) st = m;
		else dr = m-1;
	}
	if (dr > st) return -1;
	if (st == 0 && u[st] > k) return -1;
	return st;
}

void solve()
{
	int X = 0, Y = 0, pas, d, p1, p2, i;
	char ch;
	
	for (pas = 0; pas < m; ++pas)
	{
		scanf(" %c %d", &ch, &d);
		if (ch == 'N')
		{
			p1 = search1(mp(X, Y+d));
			p2 = search1(mp(X, Y));
			rez += p1-p2;
			Y += d;
		}
		if (ch == 'S')
		{
			p1 = search1(mp(X, Y-d));
			p2 = search1(mp(X, Y));
			rez += p2-p1;
			Y -= d;
		}
		if (ch == 'E')
		{
			p1 = search2(mp(Y, X+d));
			p2 = search2(mp(Y, X));
			rez += p1 - p2;
			X += d;
		}
		if (ch == 'V')
		{
			p1 = search2(mp(Y, X-d));
			p2 = search2(mp(Y, X));
			rez += p2 - p1;
			X -= d;
		}
	}
}

void writedata()
{
	printf("%Ld\n", rez);
}

int main()
{
	readdata();
	solve();
	writedata();
	return 0;
}