Cod sursa(job #358977)

Utilizator ProtomanAndrei Purice Protoman Data 25 octombrie 2009 12:29:04
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <algorithm>
#include <stdio.h>
#include <map>

#define MAX 1500000
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, m, nr, sol;
map <pair <int, int>, bool> sel;
pair <int, int> vctX[MAX], vctY[MAX];

inline int cautaC(pair <int, int> vct[], int fr, int ls, int x, int y)
{
	int med = (fr + ls) / 2;

	if ((vct[med].f > x || (vct[med].f == x && vct[med].s >= y)) && (vct[med - 1].f < x || (vct[med - 1].f == x && vct[med - 1].s < y)))
		return med;
	if (vct[med].f < x || (vct[med].f == x && vct[med].s < y))
		cautaC(vct, med + 1, ls, x, y);
	else cautaC(vct, fr, med - 1, x, y);
}

inline int cautaD(pair <int, int> vct[], int fr, int ls, int x, int y)
{
	int med = (fr + ls) / 2;

	if ((vct[med].f < x || (vct[med].f == x && vct[med].s <= y)) && (vct[med + 1].f > x || (vct[med + 1].f == x && vct[med + 1].s > y)))
		return med;
	if (vct[med].f > x || (vct[med].f == x && vct[med].s > y))
		cautaD(vct, fr, med - 1, x, y);
	else cautaD(vct, med + 1, ls, x, y);
}

int main()
{
	freopen("zc.in", "r", stdin);
	freopen("zc.out", "w", stdout);

	scanf("%d %d\n", &n, &m);

	sel[mp(0, 0)] = 1;
	for (int i = 1; i <= n; i++)
	{
		int x, y;
		scanf("%d %d\n", &x, &y);

		for (int i = x - 2; i <= x + 2; i++)
			for (int j = y - (2 - abs(i - x)); j <= y + (2 - abs(i - x)); j++)
				if (!sel[mp(i, j)])
				{
					sel[mp(i, j)] = 1;

					vctX[++nr] = mp(i, j);
					vctY[nr] = mp(j, i);
				}
	}
	vctX[0] = vctY[0] = mp(-LONG_MAX, -LONG_MAX);
	nr++;
	vctX[nr] = vctY[nr] = mp(LONG_MAX, LONG_MAX);
	sort(vctX, vctX + 1 + nr);
	sort(vctY, vctY + 1 + nr);

	for (; ; );

	int cX = 0, cY = 0;
	for (int i = 1; i <= m; i++)
	{
		char dir;
		int pasi;
		scanf("%c %d\n", &dir, &pasi);

		if (dir == 'N')
		{
			sol += cautaC(vctX, 0, nr, cX, cY + pasi) - cautaC(vctX, 0, nr, cX, cY);
			cY += pasi;
		}
		if (dir == 'S')
		{
			sol += cautaD(vctX, 0, nr, cX, cY) - cautaD(vctX, 0, nr, cX, cY - pasi);
			cY -= pasi;
		}
		if (dir == 'E')
		{
			sol += cautaC(vctY, 0, nr, cY, cX + pasi) - cautaC(vctY, 0, nr, cY, cX);
			cX += pasi;
		}
		if (dir == 'V')
		{
			sol += cautaD(vctY, 0, nr, cY, cX) - cautaD(vctY, 0, nr, cY, cX - pasi);
			cX -= pasi;
		}
	}
	if (sel[mp(cX, cY)])
		sol++;

	printf("%d\n", sol);

	fclose(stdin);
	fclose(stdout);
	return 0;
}