Cod sursa(job #641763)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 29 noiembrie 2011 13:02:50
Problema Fractal Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
/*
	impart la fiecare pas in sferturi din ce in ce mai mici
si numar sferturile intregi + puntile de legatura.

pt patrat de latura l = 2^(2l)

fiecare sfert poate avea punctul de start diferit
(transform punctul rotindu-l pentru a reveni la cazul initial)
dreptele din desen sunt lungimi intre 2 "patrate", doua puncte.
*/

#include <cstdio>

const int SUS=0,JOS=1,STANGA=2,DREAPTA=3;
const int NV=0,NE=1,SV=2,SE=3;

int n,i,j;
int pasi = 0;
int dist_sfert[4];

int lungime_patrat(int ordin)//inclusiv betisor de legatura
{
	return 1<<(2 * ordin);
}

void preprocesare()
{
	dist_sfert[NV] = 0;
	dist_sfert[SV] = 1;
	dist_sfert[SE] = 2;
	dist_sfert[NE] = 3;
}

void divide_et_impera(int n, int i, int j)
{
	if (n == 0)
		return;
	int sfert=0, i_sfert=i, j_sfert=j;

	//aducere i_sfert, j_sfert in cadranul sfertului
	if (i > 1<<(n-1))
	{
		sfert+=2;
		i_sfert -= 1<<(n-1);
	}
	if (j > 1<<(n-1))
	{
		++sfert;
		j_sfert -= 1<<(n-1);
	}

	//rotire i_sfert, j_sfert in functie de orientarea sfertului
	//(SV, SE au aceeasi orientare)


	if (sfert == NV)//transpusa
	{
		int aux = i_sfert;
		i_sfert = j_sfert;
		j_sfert = aux;
	}

	if (sfert == NE)//i simetric, j simetric => cazul NV => + transpusa
	{
		i_sfert = 1<<(n-1) - i_sfert + 1;
		j_sfert = 1<<(n-1) - j_sfert + 1;

		int aux = i_sfert;
		i_sfert = j_sfert;
		j_sfert = aux;
	}


	pasi += lungime_patrat(n-1) * dist_sfert[sfert];


	divide_et_impera(n-1,i_sfert,j_sfert);
}

int main()
{
	freopen("fractal.in","r",stdin);
	freopen("fractal.out","w",stdout);
	scanf("%d%d%d",&n,&j,&i);
	preprocesare();
	divide_et_impera(n,i,j);
	printf("%d",pasi);
	return 0;
}