Cod sursa(job #78145)

Utilizator andrei.12Andrei Parvu andrei.12 Data 15 august 2007 18:13:00
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 kb
#include<stdio.h>
#include<stdlib.h>
#define lg 1300005
#define infinit 2000000002
int nrcap, nrms, i, j, x, y, nr, xx, yy, coli, lini, colf, linf, d, pasi, li, ls, prm[lg];
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], ll[lg], cc[lg];
int comp1(const void*a, const void*b){
	int *xx = (int*)a, *yy = (int*)b;
	int x = *xx, y = *yy; 
	if (ll[x].l < ll[y].l) return -1;
	if (ll[x].l > ll[y].l) return 1;
	if (ll[x].c < ll[y].c) return -1;
	if (ll[x].c > ll[y].c) return 1;
	return 0;
}
int comp2(const void*a, const void*b){
	int *xx = (int*)a, *yy = (int*)b;
	int x = *xx, y = *yy; 
	if (cc[x].c < cc[y].c) return -1;
	if (cc[x].c > cc[y].c) return 1;
	if (cc[x].l < cc[y].l) return -1;
	if (cc[x].l > cc[y].l) return 1;
	return 0;
}
int bs1(int p, int gs){
	int li = 1, ls = nr, x, sol = 0;
	while (li <= ls){
		x = (li+ls)/2;
		if (l[x].l == p){
			if (l[x].c > gs)
				ls = x-1;
			else
				if (l[x+1].l != p || (l[x+1].l == p && l[x+1].c > gs))
					return x;
				else{
					li = x +1;
					sol = x;
				}
		}
		else
			if (l[x].l < p){
				li = x+1;
				sol = x;
			}
			else
				ls = x-1;
	}
	return sol;
}
int bs2(int p, int gs){
	int li = 1, ls = nr, x, sol = 0;
	while (li <= ls){
		x = (li+ls)/2;
		if (c[x].c == p){
			if (c[x].l > gs)
				ls = x-1;
			else
				if (c[x+1].c != p || (c[x+1].c == p && c[x+1].l > gs))
					return x;
				else{
					li = x+1;
					sol = x;
				}
		}
		else
			if (c[x].c < p){
				li = x+1;
				sol = x;
			}
			else
				ls = x-1;
	}
	return sol;
}
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){
			ll[++nr].l = y;
			ll[nr].c = x;
			cc[nr].l = y;
			cc[nr].c = x;
		}
		for (j=0; j<12; j++){
			xx = x+dx[j];
			yy = y+dy[j];
			if (xx != 0 || yy != 0){
				ll[++nr].l = yy;
				ll[nr].c = xx;
				cc[nr].l = yy;
				cc[nr].c = xx;
			}
		}
	}
	for (i=1; i<=nr; i++)
		prm[i] = i;
	qsort(prm, nr+1, sizeof(prm[0]), comp1);
	for (i=1; i<=nr; i++){
		l[i].l = ll[prm[i]].l;
		l[i].c = ll[prm[i]].c;
	}
	for (i=1; i<=nr; i++)
		prm[i] = i;
	qsort(prm, nr+1, sizeof(prm[0]), comp2);
	for (i=1; i<=nr; i++){
		c[i].l = cc[prm[i]].l;
		c[i].c = cc[prm[i]].c;
	}
	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;
			ls = bs1(linf, colf);
			li = bs1(linf, coli);
			if (ls-li)
				rezultat += ls-li;
			lini = linf;
			coli = colf;
		}
		else{
			if (dir == 'N')
				linf = lini+pasi;
			else 
				linf = lini-pasi;
			ls = bs2(colf, linf);
			li = bs2(colf, lini);
			if (ls-li)
				rezultat += ls-li;
			lini = linf;
			coli = colf;
		}
	}
	printf("%lld\n", rezultat);
	fclose(stdin);
	fclose(stdout);
	return 0;
}