Cod sursa(job #359101)

Utilizator ProtomanAndrei Purice Protoman Data 25 octombrie 2009 18:32:05
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <algorithm>
#include <stdio.h>

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

using namespace std;

int n, m, nr, sol;
bool sel[2048][2048];
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[0][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		int x, y;
		scanf("%d %d\n", &x, &y);
		x += 1000;
		y += 1000;
		if (x > 2000 || y > 2000)
			for ( ; ; );

		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[i][j])
				{
					sel[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);

	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[cX + 1000][cY + 1000])
		sol++;

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

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