Cod sursa(job #5667)

Utilizator zombie_testeala bala portocala si mandarina zombie_teste Data 13 ianuarie 2007 18:27:20
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <vector>
#include <cstdio>
#include <algorithm>
#define PB push_back
#define MP make_pair
#define UB upper_bound
#define LB lower_bound

using namespace std;

const int ND = 13;
const int cx[] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
const int cy[] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};

vector < pair <int, int> > Vx, Px, Vy, Py;

int i, j, N, M;
int x, y, x1, y1, p, ult, size;
char d;
long long Sol;

int main()
{	 
	 freopen("zc.in", "r", stdin);
	 freopen("zc.out", "w", stdout);
	 
	 vector < pair <int, int> > :: iterator it1, it2;
	 
	 scanf("%d %d", &N, &M);
	 
	 for (i = 1; i <= N; i++)
	 {
			 scanf("%d %d", &x, &y);
			 
			 for (j = 0; j < ND; j++)
			 {
					 x1 = x + cx[j];
					 y1 = y + cy[j];
					 
					 if (x1 != 0 || y1 != 0) Vx.PB( MP(x1, y1) ), Vy.PB( MP(y1, x1) );
			 }
	 }
	 	 
	 sort(Vx.begin(), Vx.end());
	 sort(Vy.begin(), Vy.end());
	 
	 Px.PB( Vx[0] );
	 ult = 0;
	 size = Vx.size();
	 
	 for (i = 1; i < size; i++)
	 {
			 if ( Px[ult].first != Vx[i].first && Px[ult].second != Vx[i].second ) Px.PB(Vx[i]), ult++;
	 }
	 
	 Py.PB( Vy[0] );
	 ult = 0;
	 size = Vy.size();
	 
	 for (i = 1; i < size; i++)
	 {
			 if ( Py[ult].first != Vy[i].first && Py[ult].second != Vy[i].second ) Py.PB(Vy[i]), ult++;
	 }
	 	 
	 /*for (it1 = Px.begin(); it1 != Px.end(); it1++) printf("%d %d\n", (*it1).first, (*it1).second);*/
	 /*for (it1 = Py.begin(); it1 != Py.end(); it1++) printf("%d %d\n", (*it1).first, (*it1).second);*/
	 
	 x = y = 0;
	 
	 for (i = 1; i <= M; ++i) 
	 {
		scanf("%c %d", &d, &p);
		
		if (d == 'S')
		{
				x1 = x; y1 = y - p;
				
				it1 = LB(Px.begin(), Px.end(), MP(x1, y1));
				
				it2 = LB(Px.begin(), Px.end(), MP(x, y));
		}
		else
		if (d == 'N')
		{
			
				x1 = x; y1 = y + p;
				
				it1 = UB(Px.begin(), Px.end(), MP(x, y));
				
				it2 = UB(Px.begin(), Px.end(), MP(x1, y1));
		}
		else
		if (d == 'V')
		{
				x1 = x - p; y1 = y;
				
				it1 = LB(Py.begin(), Py.end(), MP(y1, x1));
				
				it2 = LB(Py.begin(), Py.end(), MP(y, x));
		}
		else
		if (d == 'E')
		{
				x1 = x + p; y1 = y;
				
				it1 = UB(Py.begin(), Py.end(), MP(y, x));
				
				it2 = UB(Py.begin(), Py.end(), MP(y1, x1));
		}
		else
		{
				x1 = x; y1 = y;
				
				it1 = Px.begin(); it2 = Px.begin();
		}

		Sol += it2 - it1;
		
		x = x1; y = y1;
	}

	 printf("%lld\n", Sol);
	 
	 fclose(stdin);
	 fclose(stdout);
	 
	 return 0;
}