Solutia problemei Ultrapoligon

Prerequisites : https://infoarena.ro/problema/aria

Solutia O((2^N) * N)

Luam fiecare subpoligon si calculam aria sa.
Pentru a calcula aria unui poligon vom lua pe rand punctele si vom adauga la suma 1/2 * (x[i] * y[i + 1] - x[i + 1] * y[i]).
De asemenea, deoarece la final se cere dublul ariei, putem adauga $(x[i] * y[i + 1] - x[i + 1] * y[i])$ direct.

Solutia O(N²)

Se observa ca aria unui poligon poate fi descompusa in muchii.
Acum putem calcula pentru fiecare muchie greutatea sa (x[i] * y[i + 1] - x[i + 1] * y[i]) si sa calculam in cate subpoligoane se afla.
Numarul de subpoligoane in care se afla muchia i,j cu i < j este 2 ^ (n - (j - i + 1)). Calculam intr-un mod asemanator si pentru muchiile cu j < i

Solutia O(N)

Se observa ca si aria unei muchii este compusa din 2 componente, anume:
x[i] * y[i + 1] si - x[i + 1] * y[i]
Vom rezolva pentru x[i] * y[i + 1] iar pentru cealalta se poate rezolva analog (Detaliu de implementare: eu am dat swap la x si y si am schimbat la final semnul)
Observam ca putem da factor comun pe x[i], mai intai vom calcula pentru i = 1 si obtinem:
x¹ * (y² * 2 ^{(n - 2) + y3 * 2} (n - 3) + ... y[n] * 2 ^{(n - n)).} Pentru a calcula pentru urmatorul i observam ca partea din paranteza se inmulteste cu 2 si se scade y[i] * 2 (n - 1) din ea.