Cod sursa(job #77741)

Utilizator andrei.12Andrei Parvu andrei.12 Data 14 august 2007 19:03:51
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.69 kb
#include<stdio.h>
#include<stdlib.h>
#define lg 100005
#define infinit 2000000002
int nrcap, nrms, i, j, x, y, nr, xx, yy, coli, lini, colf, linf, d, pasi, li, ls;
char dir;
long long rezultat;
const int dx[]={0, 0, 0, 0, 1, -1, 1, -1, 1, 2, -1, -2};
const int dy[]={1, 2, -1, -2, 1, 1, -1, -1, 0, 0, 0, 0};
struct ches{
	int c, l;
};
ches l[lg], c[lg];
int comp1(const void*a, const void*b){
	ches x = *(ches*)a, y = *(ches*)b;
	if (x.l < y.l) return -1;
	if (x.l > y.l) return 1;
	if (x.c < y.c) return -1;
	if (x.c > y.c) return 1;
	return 0;
}
int comp2(const void*a, const void*b){
	ches x = *(ches*)a, y = *(ches*)b;
	if (x.c < y.c) return -1;
	if (x.c > y.c) return 1;
	if (x.l < y.l) return -1;
	if (x.l > y.l) return 1;
	return 0;
}
int bsegal1(int caut, int val) //minimul
{
	int li = 1, ls = nr, p, min = infinit;
	if (!val){
		while (li <= ls){
			p = (li+ls)/2;
			if (l[p].l < caut)
				li = p+1;
			else
				if (l[p].l > caut)
					ls = p-1;
				else{
					if (p < min)
						min = p;
					ls = p-1;
				}
		}
		return min;
	}
	else{
		while (li <= ls){
			p = (li+ls)/2;
			if (c[p].c < caut)
				li = p+1;
			else
				if (c[p].c > caut)
					ls = p-1;
				else{
					if (p < min)
						min = p;
					ls = p-1;
				}
		}
		return min;
	}
}
int bsegal2(int caut, int val) //maximul
{
	int li = 1, ls = nr, p, max = -1;
	if (!val){
		while (li <= ls){
			p = (li+ls)/2;
			if (l[p].l < caut)
				li = p+1;
			else
				if (l[p].l > caut)
					ls = p-1;
				else{
					if (p > max)
						max = p;
					li = p+1;
				}
		}
		return max;
	}
	else{
		while (li <= ls){
			p = (li+ls)/2;
			if (c[p].c < caut)
				li = p+1;
			else
				if (c[p].c > caut)
					ls = p-1;
				else{
					if (p > max)
						max = p;
					li = p+1;
				}
		}
		return max;
	}
}
int caut(int li, int ls, int gst, int val){
	int p, tt = li, cc = ls;
	if (!val){
		while (li <= ls){
			p = (li+ls)/2;
			if (l[p].c > gst)
				ls = p-1;
			else
				if (l[p].c <= gst)
					if (l[p+1].c > gst)
						return p;
					else
						li = p+1;
		}
		if ((li+ls) / 2 >= cc)
			return cc-tt+1;
		else
			return 0;
	}
	else{
		while (li <= ls){
			p = (li+ls)/2;
			if (c[p].l > gst)
				ls = p-1;
			else
				if (c[p].l <= gst)
					if (c[p+1].l > gst)
						return p;
					else
						li = p+1;
		}
		if ((li+ls) / 2 >= cc)
			return cc-tt+1;
		else
			return 0;
	}
}
int main()
{
	freopen("zc.in","r",stdin);
	freopen("zc.out","w",stdout);
	scanf("%d%d", &nrcap, &nrms);
	for (i=1; i<=nrcap; i++){
		// x coloana si y linia
		scanf("%d%d\n", &x, &y);
		if (x != 0 && y != 0){
			l[++nr].l = y;
			l[nr].c = x;
			c[nr].l = y;
			c[nr].c = x;
		}
		for (j=0; j<12; j++){
			xx = x+dx[j];
			yy = y+dy[j];
			if (xx != 0 && yy != 0){
				l[++nr].l = yy;
				l[nr].c = xx;
				c[nr].l = yy;
				c[nr].c = xx;
			}
		}
	}
	qsort(l, nr+1, sizeof(l[0]), comp1);
	qsort(c, nr+1, sizeof(c[0]), comp2);
	coli = 0;
	lini = 0;
	colf = 0;
	linf = 0;
	for (i=1; i<=nrms; i++){
		scanf("%c", &dir);
		scanf("%d\n", &pasi);
		if (dir == 'E' || dir == 'V'){
			if (dir == 'E')
				colf = coli+pasi;
			else
				colf = coli-pasi;
			li = bsegal1(lini, 0);
			ls = bsegal2(lini, 0);
			if (li != infinit && ls != -1)
				rezultat += caut(li, ls, colf, 0)-caut(li, ls, coli, 0);
			coli = colf;
		}
		else{
			if (dir == 'N')
				linf = lini+pasi;
			else 
				linf = lini-pasi;
			li = bsegal1(coli, 1);
			ls = bsegal2(coli, 1);
			if (li != infinit && ls != -1)
				rezultat += caut(li, ls, linf, 1)-caut(li, ls, lini, 1);
			lini = linf;
		}
	}
	printf("%lld\n", rezultat);
	fclose(stdin);
	fclose(stdout);
	return 0;
}