Cod sursa(job #5683)

Utilizator mockeBarca Cristian Mihai mocke Data 13 ianuarie 2007 19:36:20
Problema Zota & Chidil Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 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 T = 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;

void remake( vector < pair <int, int> > *A, vector < pair <int, int> > *B)
{
	 int i;
	 (*A).PB( (*B)[0] );
	 ult = 0;
	 size = (*B).size();
	 
	 for (i = 1; i < size; i++)
	 {
			 if ( (*A)[ult] == (*B)[i] ) continue;
			 
			 (*A).PB((*B)[i]), ult++;
	 }
}


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 < T; 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());
	 
	 remake(&Px, &Vx);
	 remake(&Py, &Vy);
	 	 
	 /*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 == 'N')
		{
				x1 = x; y1 = y + p;
				
				it1 = UB(Px.begin(), Px.end(), MP(x, y));
				
				it2 = LB(Px.begin(), Px.end(), MP(x1, y1));
		}
		else
		if (d == 'S')
		{
				x1 = x; y1 = y - p;
				
				it1 = UB(Px.begin(), Px.end(), MP(x1, y1));
				
				it2 = LB(Px.begin(), Px.end(), MP(x, y));
		}
		else
		if (d == 'E')
		{
				x1 = x + p; y1 = y;
				
				it1 = UB(Py.begin(), Py.end(), MP(y, x));
				
				it2 = LB(Py.begin(), Py.end(), MP(y1, x1));
		}
		else
		if (d == 'V')
		{
				x1 = x - p; y1 = y;
				
				it1 = UB(Py.begin(), Py.end(), MP(y1, x1));
				
				it2 = LB(Py.begin(), Py.end(), MP(y, x));
		}
		
		Sol += it2 - it1;
		
		x = x1; y = y1;
		
		it1 = Px.begin(); it2 = Px.begin();
		
	}

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