Cod sursa(job #705652)

Utilizator IronWingVlad Paunescu IronWing Data 4 martie 2012 18:34:21
Problema Fractal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>

inline int pow2(int k){
	/* returns the 2^k */
	return 1 << k ;
}

int getNoSteps(int k, int l, int c){
	/* function which determines the number of steps of the space filling Hilbert curve of order k
	   that covers every point of the grid in the space 2^k * 2^k */
	
	if(k == 0){
		return 0;
	}
	/* if the fractal can be decomposed in 4 quadrants:
		   1 4
		   2 3		
		*/
	/*determine what quadrant the point (x,y) resides in */
	int med = pow2(k-1), quadLen = med * med - 1;
	if(l <= med && c <= med){
		/* first quadrant, rotated and flipped */
		/*adjust the coordinates */
		return 0 + getNoSteps(k - 1, c, l);
	}
	if(l > med && c <= med){
		/* second quadrant */
		/* add the length of one quadrant of k-1 order + 1 link, and adjust the coordinates */
		return 1 + quadLen + getNoSteps(k - 1, l - med, c);
		}
	if(l > med && c > med){
		/* third quadrant */		
		/* add the length of two quadrants of k-1 order + 2 links, and adjust the coordinates */
		return 2 + 2 * quadLen + getNoSteps(k - 1, l - med, c - med);
	}

	if(l <= med && c > med){
		/* fourth quadrant, rotated and flipped */
		/* add the length of three quadrants of k-1 order + 3 links, and adjust the coordinates */
		return 3 + 3 * quadLen + getNoSteps(k - 1, 2 * med - c  + 1 , med - l + 1);
	}
}

int main(){		
	int k, x, y;	
	std::ifstream("fractal.in")>>k>>x>>y;
	std::ofstream("fractal.out")<<getNoSteps(k,y,x);
		
	return 0;
}