Cod sursa(job #705639)

Utilizator IronWingVlad Paunescu IronWing Data 4 martie 2012 18:15:06
Problema Fractal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>

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

int getNoSteps(int k, int x, int y){
	/* 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;
	if(x <= med && y <= med){
		/* first quadrant, rotated 90 degrees counterclockwise */
		/*adjust the coordinates */
		return 0 + getNoSteps(k - 1, med -  y + 1, x);
	}
	if(x <= med && y > 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, x, y - med);
		}
	if(x > med && y > 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, x - med, y - med);
	}

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

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