Proiect AF - Secționare hârtie (Gaură cub)

/*
https://codingcompetitions.withgoogle.com/codejam/round/00000000000000cb/00000000000079cc#problem
PROBLEMĂ

Un cub este lăsat să cadă printr-o hârtie subțire. Hârtia reprezintă un plan într-un spațiu tridimensional, are coordonata Y = -10 m
și este paralelă cu axele X și Z. Cubul își are centrul în punctul (0, 0, 0), laturile sale au lungimea de 1 m, iar colțurile sale
au coordonatele (+/- 0.5, +/- 0.5, +/- 0.5). În căderea sa, cubul nu se rotește, iar traiectoria căderii sale este perpendiculară
pe planul X Z. La impact, cubul trece prin hârtie și lasă în urma sa o gaură ce ia forma proiecției cubului pe planul
hârtiei. Găsiți un mod de a roti cubul așa încât să lase pe hârtie o gaură de arie A m^2. Exprimați rotația folosind trei puncte
din spațiu: centrele a trei fețe ale cubului ce formează un colț.
*/

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

void ProdusMatrice3x3(double matA[3][3], double matB[3][3], double rezultat[3][3]) // Calculeaza produsul matricilor matA si matB.
{                                                                                  // Produsul este memorat in matricea rezultat.
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            rezultat[i][j] = matA[i][0] * matB[0][j] + matA[i][1] * matB[1][j] + matA[i][2] * matB[2][j];
}

void rezolvare(double A, double solutie[3][3])
{
    const double sqrt2 = sqrt(double(2));
    const double sqrtHalf = sqrt(double(0.5));
    // Constantele sqrt2 si sqrtHalf au fost initializate pentru usurarea calculelor de mai jos.

    double rotate45[3][3]
    {
        sqrtHalf, 0, sqrtHalf,
        0, 1, 0,
        -sqrtHalf, 0, sqrtHalf
    };

    // Pentru a roti cubul tridimensional vom folosi matrice de rotatie.
    // Matricea rotate45 este utilizata pentru a roti cubul cu 45 de grade pe axa Y.
    // rotate45 are ca scop usurarea determinarii unei proiectii a cubului ce are aria (aproape) A.

    // Fiind o problema care cere doar o solutie posibila, aceasta poate fi rezolvata in mai multe moduri. Pot fi mai mutle output-uri
    // corecte pentru acelasi input.

    // Metoda propusa este urmatoarea: Cubul este initial rotit cu 45 de grade pe axa Y. Rotirile subsecvente vor avea loc pe axa Z,
    // in urma carora proiectia cubului pe plan va avea forma unui hexagon. Hexagonul va fi alcatuit din 2 triunghiuri isoscele egale
    // si un dreptunghi (in cazul in care proiectia cubului este un patrat, va fi considerat ca fiind un hexagon cu latimea dreptunghiului
    // egala cu 0 m; daca este un dreptunghi, va fi considerat ca fiind un hexagon cu inaltimile triunghiurilor egale cu 0 m). Triunghiurile
    // pot fi rearanjate asa incat hexagonul devine un dreptunghi (*). Se determina matematic ca dreptunghiul rezultat are lungimea egala cu sqrt(2)
    // si latimea egala cu sqrt(2)/2*cos(Alfa)+sin(Alfa), unde Alfa este unghiul de rotatie pe axa Z. Stiind ca aria dreptunghiului este A,
    // putem determina sin(Alfa) si cos(Alfa), cu ajutorul carora aflam matricea de rotatie pe axa Z.

    const double sqrtDelta = sqrt(3 - A * A); // Se ajunge la o ecuatie de gradul 2 unde x = sin(Alfa). Prin calcul se ajunge la Delta = 3 - A^2.
    const double cosAlfa = (A + sqrtDelta * sqrt2) / 3;
    const double sinAlfa = (A * sqrt2 - sqrtDelta) / 3;
    double rezultat[3][3] = { cosAlfa, sinAlfa, 0, -sinAlfa, cosAlfa, 0, 0, 0, 1 }; // rezultat este matricea de rotatie pe axa Z pentru unghiul Alfa.

    ProdusMatrice3x3(rotate45, rezultat, solutie); // Solutia consta in produsul matricelor rotate45 si rezultat.
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            solutie[i][j] /= 2;

    // Elementele matricei solutie se impart la 2 deoarece matricea initiala a cubului este egala cu 0.5 * matricea unitate.
    // ( Deoarece pozitia initiala a centrului cubului este (0,0,0), iar centrele a trei fete ale cubului ce formeaza un colt sunt
    // (0.5, 0, 0), (0, 0.5, 0) si (0, 0, 0.5) ).
}

int main()
{
    double A, C[3][3];
    cout << "A = ";
    cin >> A; // A = aria gaurii formate

    if (A >= 1 && A <= sqrt(3)) // 1 <= A <= 1.732050
    {
        rezolvare(A, C);
        for (int i = 0; i < 3; i++) // Afisarea celor 3 puncte prin care se exprima rotatia cubului.
        {
            for (int j = 0; j < 3; j++)
                cout << setw(9) << C[i][j] << ' ';
            cout << '\n';
        }
    }
    else
        cout << "Eroare: Aria nu poate avea valoarea data!";
    return 0;
}

// OBSERVATII:
// - Coordonata Y a planului hartiei nu influenteaza solutia;
// - Se observa faptul ca aria proiectiei cubului este minima cand are forma de patrat (A = 1) si maxima cand are forma de hexagon regulat (A = sqrt(3));
// - Deoarece nu sunt utilizate structuri repetitive ce depind de valori date de la tastatura, algoritmul se rezolva in timp constant O(1).
// - (*) Unul dintre cele doua triunghiuri va fi taiat in doua triunghiuri egale, care sunt atasate la celalalt triunghi pentru a forma un dreptunghi.