Cod sursa(job #432855)

Utilizator nandoLicker Nandor nando Data 2 aprilie 2010 20:31:39
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <utility>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;

#define NDIR 13

vector< pair<int,int> > vx, vy;
typedef vector<pair<int,int> >::iterator iter;
int n,m;

int dir[][2]={  {-2, 0},
        {-1,-1},{-1, 0},{-1,+1},
{ 0,-2},{ 0,-1},{ 0, 0},{ 0,+1},{ 0,+2},
	    {+1,-1},{+1, 0},{+1,+1},
			    {+2,0}};

void addPoint(int x,int y){
	for(int i=0;i<NDIR;i++){
		if(x+dir[i][0]!=0||y+dir[i][1]!=0){
			vx.push_back(make_pair(x+dir[i][0],y+dir[i][1]));
			vy.push_back(make_pair(y+dir[i][1],x+dir[i][0]));
		}
	}
}

bool compPts(pair<int,int> p1, pair<int,int> p2){
	return ((p1.first!=p2.first)?(p1.first<p2.first):(p1.second<p2.second));	
}

bool equPts(pair<int,int> p1, pair<int,int> p2){
	return (p1.first==p2.first&&p1.second==p2.second);
}

int main(){
	fstream fin("zc.in",ios::in);
	fstream fout("zc.out",ios::out);

	fin>>n>>m;

	int x,y,l,nb=0,b,e;
	char dir;
	for(int i=0;i<n;i++){
		fin>>x>>y;
		addPoint(x,y);
	}

	sort(vx.begin(),vx.end(),compPts);
	sort(vy.begin(),vy.end(),compPts);
	iter it;

	it=unique(vx.begin(),vx.end(),equPts);
	vx.resize(it-vx.begin());

	it=unique(vy.begin(),vy.end(),equPts);
	vy.resize(it-vy.begin());


	x=y=0;
	for(int i=0;i<m;i++){
		fin>>dir>>l;
		switch(dir){
			case 'N':
				b=lower_bound(vx.begin(),vx.end(),make_pair(x,y+1),compPts)-vx.begin();
				e=upper_bound(vx.begin(),vx.end(),make_pair(x,y+l),compPts)-vx.begin();
				if(e>=b&&vx[b].first==x&&y<=vx[b].second&&vx[b].second<=y+l){
					nb+=e-b;
				}
				y+=l;
				break;
			case 'V':
				b=lower_bound(vy.begin(),vy.end(),make_pair(y,x-l),compPts)-vy.begin();
				e=upper_bound(vy.begin(),vy.end(),make_pair(y,x-1),compPts)-vy.begin();
				if(e>=b&&vy[b].first==y&&x-l<=vy[b].second&&vy[b].second<=x){
					nb+=e-b;	
				}

				x-=l;
				break;
			case 'S':
				b=lower_bound(vx.begin(),vx.end(),make_pair(x,y-l),compPts)-vx.begin();
				e=upper_bound(vx.begin(),vx.end(),make_pair(x,y-1),compPts)-vx.begin();
				if(e>=b&&vx[b].first==x&&y-l<=vx[b].second&&vx[b].second<=y){
					nb+=e-b;
				} 
				y-=l;
				break;
			case 'E':
				b=lower_bound(vy.begin(),vy.end(),make_pair(y,x+1),compPts)-vy.begin();
				e=upper_bound(vy.begin(),vy.end(),make_pair(y,x+l),compPts)-vy.begin();
				if(e>=b&&vy[b].first==y&&x<=vy[b].second&&vy[b].second<=x+l){
					nb+=e-b;
				}
				x+=l;
				break;
		}
		printf("%d %d %d\n",x,y,e-b);
	}

	fout<<nb;

	fin.close();
	fout.close();
	return 0;
}