Cod sursa(job #1816529)

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

using namespace std;

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;
}

pair<int, int> reduCadranul1(pair<int, int> punct, int raza)
{
	swap(punct.first, punct.second);

	return punct;
}

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(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(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;
}