Cod sursa(job #359138)

Utilizator ProtomanAndrei Purice Protoman Data 25 octombrie 2009 20:30:51
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <algorithm>
#include <stdio.h>
#include <vector>

#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, m, nr, sol;
vector <pair <int, int> > vctX, vctY;

inline int cautaC(vector <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))
		return cautaC(vct, med + 1, ls, x, y);
	else return cautaC(vct, fr, med - 1, x, y);
}

inline int cautaD(vector <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))
		return cautaD(vct, fr, med - 1, x, y);
	else return 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);

	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 (i || j)
					vctY.pb(mp(i, j));
	}
	vctY.pb(mp(LONG_MAX, LONG_MAX));
	vctY.pb(mp(-LONG_MAX, -LONG_MAX));
	sort(vctY.begin(), vctY.end());

	vctX.pb(vctY[0]);
	for (int i = 1 ; i < vctY.size(); i++)
		if (vctY[i] != vctY[i - 1])
			vctX.pb(vctY[i]);
	vctY.clear();
	for (int i = 0; i < vctX.size(); i++)
		vctY.pb(mp(vctX[i].s, vctX[i].f));

	sort(vctY.begin(), vctY.end());

	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, vctX.size() - 1, cX, cY + pasi);
			sol -= cautaC(vctX, 0, vctX.size() - 1, cX, cY);
			cY += pasi;
		}
		if (dir == 'S')
		{
			sol += cautaD(vctX, 0, vctX.size() - 1, cX, cY) - cautaD(vctX, 0, vctX.size() - 1, cX, cY - pasi);
			cY -= pasi;
		}
		if (dir == 'E')
		{
			sol += cautaC(vctY, 0, vctY.size() - 1, cY, cX + pasi) - cautaC(vctY, 0, vctY.size() - 1, cY, cX);
			cX += pasi;
		}
		if (dir == 'V')
		{
			sol += cautaD(vctY, 0, vctY.size() - 1, cY, cX) - cautaD(vctY, 0, vctY.size() - 1, cY, cX - pasi);
			cX -= pasi;
		}
	}
	if (vctX[cautaC(vctX, 0, vctX.size() - 1, cX, cY)] == mp(cX, cY))
		sol++;

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

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