#include
#include
using namespace std;
set S;
long long frecv[4], v[] = {3,4,5,8,10,12,14,32,57,64};
/** Codificare :
0 - nu folosim,
1 - face parte din latura a
2 - face parte din latura b
3 - face parte din latura c
in frecv[i] vom retine suma tuturor numerelor
ce adunate formeaza o latura din triunghi.
*/
/** Putem folosi baza 4 pentru a
parcurge toate posibilitatile.
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
...
3 3 3 3 3 3 3 3 3 3
Pentru fiecare element din v[]
ii corespunde pozitia cifrei din
reprezentarea in baza 4.
*/
/**
Folosind 2 biti putem reprezenta o cifra din baza 4 :
0 (4) -> 00 (2)
1 (4) -> 01 (2)
2 (4) -> 10 (2)
3 (4) -> 11 (2)
*/
/**
Pentru a obtine ultimii 2 biti putem folosi
(n % 4) sau (n & 3) (sunt echivalente)
Putem imparti la 2^n folosind (1 >> n)
si implicit prin 4^n folosind (1 >> (2*n))
Consideram ca cifrele din baza 4 sunt notate astfel :
_ _ _ _ _ _ _ _ _ _
0 1 2 3 4 5 6 7 8 9
Asadar putem afla cifra x din reprezentarea in baza 4 a lui i astfel :
(i >> (2 * x)) % 4 .
Adica mai intai impartim i prin 4^x si apoi luam ultimii 2 biti.
(La fel cum in baza 10 impartind prin 10^x taiem ultimele x cifre din baza 10,
impartind prin 4^x taiem ultimele x cifre din baza 4).
*/
int main()
{
for(int i = 0;i<(1<<20);i++)
{
/// i este numarul pe care il descompunem in baza 4.
///resetam valorile din frecv.
for(int j = 0;j<4;j++)
frecv[j] = 0;
/// pe baza descompunerii in baza 4 adunam unde trebuie v[j].
for(int j = 0;j<10;j++)
{
int nrelem = ((i >> (2*j)) % 4);
frecv[nrelem] += v[j];
}
/**
Conditia (1) :
Intr-un triunghi se respecta mereu relatia
a < b + c (unde a,b,c sunt lungimile laturilor.)
Acum verificam daca aria este
valida folosind formula lui Heron.
Aria = sqrt(p*(p-a)*(p-b)*(p-c)) , unde p = (a+b+c)/2
Scapam de radical, ridicand la puterea a doua.
Aria^2 = p*(p-a)*(p-b)*(p-c).
p poate avea virgula (.5) deci trebuie sa facem o modificare a formulei
si sa transformam p in 2*p in fiecare factor.
Aria^2 * ceva = 2 * p * 2 ( p - a ) * 2 * (p - b) * 2 * (p - c)
Evident acest "ceva" va fi 2 * 2 * 2 * 2 = 16
Aria^2 * 16 = 2p *(2p - 2a) * (2p - 2b) * (2p - 2c).
... Am scapat astfel de problema virgulei.
Conditia (2) :
Trebuie sa ne asiguram ca factorii ( 2p - 2a) , (2p - 2b), (2p - 2c) sunt toti pozitivi
(In cod 2p va fi P = a + b + c.)
*/
long long P = frecv[1] + frecv[2] + frecv[3];
bool valid = true;
/// Verificam pe rand cele doua conditii.
// metoda 1 : if-uri
/*
if(frecv[1] >= frecv[2] + frecv[3]) valid = false;
if(frecv[2] >= frecv[1] + frecv[3]) valid = false;
if(frecv[3] >= frecv[1] + frecv[2]) valid = false;
if(P - 2*frecv[1] <= 0) valid = false;
if(P - 2*frecv[2] <= 0) valid = false;
if(P - 2*frecv[3] <= 0) valid = false;
*/
// metoda 2 : for - cu termeni generali
/*
n % 3 = {0,1,2}.
n % 3 + 1 = {1,2,3}.
si atunci in loc de (n) putem inlocui cu (n+1) si (n+2)
pentru a obtine ceilalti doi termeni din multimea {1,2,3}.
Spre exemplu, daca avem j = 2 :
(2 % 3) + 1 = 3 (n)
((2+1) % 3) + 1 = 1 (n+1)
((2+2) % 3) + 1 = 2 (n+2)
*/
for(int j = 0; j < 3 && valid; j++)
{
/// Conditia 1 :
if(frecv[j % 3 + 1] >= frecv[(j+1) % 3 + 1] + frecv[(j+2) % 3 + 1])
valid = false;
/// Conditia 2 :
if(P - 2 * frecv[j + 1] <= 0) /// (j + 1) - > {1, 2, 3}
valid = false;
}
/// Daca avem o arie valida o calculam si o punem in set.
if(valid)
{
/// Acum de fapt calculam (aria^2 * 16) .. dupa cele explicate mai sus.
long long aria = P * (P - 2*frecv[1]) * (P - 2*frecv[2]) * (P - 2*frecv[3]);
S.insert(aria);
}
}
cout << S.size() << '\n';
return 0;
}