Pagini recente » Cod sursa (job #2546268) | Cod sursa (job #775520) | Cod sursa (job #1006241) | Cod sursa (job #688571) | Cod sursa (job #983288)
Cod sursa(job #983288)
#include <cstdio>
#include <stdlib.h>
#include <math.h>
using namespace std;
int k, x, y, size[16];
void init(){
// compute sizes of all degrees
size[0] = 0;
for(int i = 1; i <= 15; ++i)
size[i] = size[i-1] * 4 + 3;
}
int computeNrSteps(int _k, int _x, int _y){
//printf("%d %d %d\n", _k, _x, _y);
// anchor _k == 1
if(_k == 1){
if(_x == 1 && _y == 1)
//quadrant I
return 0;
else if(_x == 1 && _y == 2)
//quadrant II
return 1;
else if(_x == 2 && _y == 2)
//quadrant III
return 2;
else if(_x == 2 && _y == 1)
//quadrant IV
return 3;
else
throw("_k == 1 wrong coordinates");
};
// recursion
int half = pow(2, _k - 1);
if(_x <= half && _y <= half)
//quadrant I - no additional steps
//point needs to be rotated right and y-inverted for k-1 fractal
return computeNrSteps(_k - 1, _y, _x) + 0;
else if(_x <= half && _y >= half + 1)
//quadrant II - one additional k-1 fractal steps + 1
//point doesn't have to be rotated, just scaled for k-1 fractal
return computeNrSteps(_k - 1, _x, _y - half) + size[_k - 1] + 1;
else if(_x >= half + 1 && _y >= half + 1)
//quadrant III - two additional k-1 fractal steps + 2
//both x and y scaled for k-1 fractal
return computeNrSteps(_k - 1, _x - half, _y - half) + size[_k - 1]*2 +2;
else if(_x >= half + 1 && _y <= half)
//quadrant IV - three addtitiona k-1 fractal steps + 3
//point rotated left and y-inverted for k-1 fractal
return computeNrSteps(_k -1 , half - _y + 1, pow(2, _k) - _x + 1) + size[_k - 1]*3 + 3;
else
throw("recursion error");
}
int main(){
freopen("fractal.in", "r", stdin);
freopen("fractal.out", "w", stdout);
//read
scanf("%d %d %d", &k, &x, &y);
//initialize size vector
init();
int nrSteps = computeNrSteps(k, x, y);
printf("%d", nrSteps);
fclose(stdin);
fclose(stdout);
}