Cod sursa(job #1816515)

Utilizator dcutitoiuCutitoiu Adrian-Nicolae dcutitoiu Data 26 noiembrie 2016 16:12:34
Problema Fractal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <stdio.h>
#include <math.h>
#include <vector>
#include <string.h>
#include <iostream>
#include <fstream>

using namespace std;

void incarcare(int curbe[])
{
	curbe[1] = 3;
	int i;
	for (i = 2; i <= 15; i++)
		curbe[i] = curbe[i - 1] * 4 + 3;
}
vector<int> incarcare(int ordin)
{
	vector<int> lungimi(ordin + 1);
	lungimi[1] = 3;

	for (int i = 2; i <= ordin; ++i)
		lungimi[i] = lungimi[i - 1] * 4 + 3;

	return lungimi;
}
void reduCadranul1(int *x, int *y, int raza) {
	int aux;
	aux = *x;
	*x = *y;
	*y = aux;
}
pair<int, int> reduCadranul1(pair<int, int> punct, int raza)
{
	swap(punct.first, punct.second);

	return punct;
}
void reduCadranul4(int *x, int *y, int raza) {
	*x = 2 * raza - *x + 1;
	*y = raza - *y + 1;
	int aux = *x;
	*x = *y;
	*y = aux;
}
pair<int, int> reduCadranul4(pair<int, int> punct, int raza)
{
	punct.first = 2 * raza - punct.first + 1;
	punct.second = raza - punct.second + 1;
	swap(punct.first, punct.second);

	return punct;
}
pair<int, int> reduCadranul2(pair<int, int> punct, int raza)
{
	punct.second = punct.second - raza;
	return punct;
}
pair<int, int> reduCadranul3(pair<int, int> punct, int raza)
{
	punct.second = punct.second - raza;
	punct.first = punct.first - raza;
	return punct;
}
int determinaCadran(int *x, int *y, int r) {
	if (*x <= r)
		if (*y <= r) {
			reduCadranul1(x, y, r);
			return 1;
		}
		else {
			*y = *y - r;
			return 2;
		}
	else
		if (*y <= r) {
			reduCadranul4(x, y, r);
			return 4;
		}
		else {
			*x = *x - r;
			*y = *y - r;
			return 3;
		}
}
int DeterminaCadran(pair<int, int> punct, int raza)
{
	return punct.first <= raza
		? punct.second <= raza
		? 1
		: 2
		: punct.second <= raza
		? 4
		: 3;
}
pair<int, int> ReduCadran(pair<int, int> punct, int raza)
{
	int cadran = DeterminaCadran(punct, raza);

	switch (cadran)
	{
	case 1:
		return reduCadranul1(punct, raza);
	case 2:
		return reduCadranul2(punct, raza);
	case 3:
		return reduCadranul3(punct, raza);
	case 4:
		return reduCadranul4(punct, raza);
	}
}
int fractal(int x, int y, int ordin, int curbe[]) {
	int cadran, raza = pow(2, ordin - 1);
	if (ordin == 1) {
		if (x == 1 && y == 1)
			return 0;
		if (x == 1 && y == 2)
			return 1;
		if (x == 2 && y == 2)
			return 2;
		return 3;
	}

	cadran = determinaCadran(&x, &y, raza);
	return (cadran - 1)*curbe[ordin - 1] + cadran - 1 + fractal(x, y, ordin - 1, curbe);
}
int fractal(pair<int, int> punct, int ordin, vector<int> & lungimi)
{
	int raza = (1 << (ordin - 1));
	int cadran = DeterminaCadran(punct, raza);

	if (ordin == 1)
	{
		return DeterminaCadran(punct, 1) - 1;
	}

	int curbeParcurse = cadran - 1;
	int lungimeCurbeParcurse = curbeParcurse * lungimi[ordin - 1];
	auto punctUrmator = ReduCadran(punct, raza);

	return lungimeCurbeParcurse + curbeParcurse + fractal(punctUrmator, ordin - 1, lungimi);
}
int main() {
	int k, a, b, i;
	ifstream in("fractal.in");
	ofstream out("fractal.out");

	in >> k >> a >> b;

	auto x = incarcare(k);

	out << fractal({ a,b }, k, x);
	return 0;
}