Pagini recente » Cod sursa (job #2984520) | Cod sursa (job #955808) | Cod sursa (job #1521112) | Cod sursa (job #553561) | Cod sursa (job #705639)
Cod sursa(job #705639)
#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;
}