Pagini recente » Cod sursa (job #3219301) | Cod sursa (job #2061388) | Cod sursa (job #1384392) | Cod sursa (job #2596824) | Cod sursa (job #705652)
Cod sursa(job #705652)
#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;
}