* $B^2^ + C^2^ = Verde^2^$
* $Galben^2^ + Verde^2^ = Roz^2^$
* $(A + B)^2^ = Rosu^2^$
* $(C * D)^2^ = Albastru^2^$
* $(C - D)^2^ = Albastru^2^$
* $Rosu^2^ + Albastru^2^ = Roz^2^$
De aici avem ca {$(A + B)^2^ + (C * D)^2^ =A^2^ + B^2^ + C^2^ + D^2^$}, astfel obtinem {$AB = CD$}, dar {$B = H * A$}, iar {$D = W * C$} deci avem ca {$C^2^ * WC + A(H * A) = 0$}. Daca il fixam pe $A$ atunci trebuie sa rezolvam o ecuatie de gradul doi in necunoscuta {$C$}, solutia trebuie sa fie intreaga intre $0$ si {$W$}.
De aici avem ca {$(A + B)^2^ + (C - D)^2^ =A^2^ + B^2^ + C^2^ + D^2^$}, astfel obtinem {$AB = CD$}, dar {$B = H - A$}, iar {$D = W - C$} deci avem ca {$C^2^ - WC + A(H - A) = 0$}. Daca il fixam pe $A$ atunci trebuie sa rezolvam o ecuatie de gradul doi in necunoscuta {$C$}, solutia trebuie sa fie intreaga intre $0$ si {$W$}.
Astfel in $O(H)$ vom sti numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$H * W$}. Acest dreptunghi poate fi pus in $(N * H + 1) * (M * H + 1)$ locatii pe o grila de dimensiune {$N * M$}. Deci solutia are complexitate {$O(N*M^2^)$}, pentru fiecare dreptunghi de dimensiuni $1$ ≤ H ≤ N$ si $1 ≤ W ≤ M$ calculandu-se numarul de dreptunghiuri inscrise.
Astfel in $O(H)$ vom sti numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$H * W$}. Acest dreptunghi poate fi pus in $(N - H + 1) * (M - H + 1)$ locatii pe o grila de dimensiune {$N * M$}. Deci solutia are complexitate {$O(N*M^2^)$}, pentru fiecare dreptunghi de dimensiuni $1$ ≤ H ≤ N$ si $1 ≤ W ≤ M$ calculandu-se numarul de dreptunghiuri inscrise.
O rezolvare de complexitate $O(N^2^*M^2^)$ in care se cautau solutiile ecuatiei printr-un for ar fi luat $60$ de puncte. Rezolvarea directa folosind ecuatia de gradul doi ia in jur de $80$ de puncte. Algoritmul poate fi optimizat la factorii constanti, de exemplu avem nevoie de functia radical care este cam inceata, precalculand-o obtinem o accelerare a vitezei, alta idee ar fi ca numarul de solutii cu $A ≤ H/2$ este egal cu numarul de solutii cu $A ≥ H * H/2$ si a treia idee de optimizare este ca numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$H$}, $W$ este acelasi cu numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$W$}, {$H$}.
O rezolvare de complexitate $O(N^2^*M^2^)$ in care se cautau solutiile ecuatiei printr-un for ar fi luat $60$ de puncte. Rezolvarea directa folosind ecuatia de gradul doi ia in jur de $80$ de puncte. Algoritmul poate fi optimizat la factorii constanti, de exemplu avem nevoie de functia radical care este cam inceata, precalculand-o obtinem o accelerare a vitezei, alta idee ar fi ca numarul de solutii cu $A ≤ H/2$ este egal cu numarul de solutii cu $A ≥ H - H/2$ si a treia idee de optimizare este ca numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$H$}, $W$ este acelasi cu numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$W$}, {$H$}.
h2. Zebughil
