* $1 ≤ N ≤ 100 000$
* $-1 000 000 ≤ x$~$i$~, $y$~$i$~ $≤ 1 000 000$

* Rezultatul se va afişa cu o precizie de $10^-5^$.

* Rezultatul se va afişa cu o precizie de $10^-4^$.

h2. Exemplu

h2. Indicaţii de rezolvare

Desi problema are ca date de intrare poligoane convexe, rezolvarea de mai jos este valabila pentru orice tip de poligoane. Pentru a calcula aria unui poligon {$A{~1~}A{~2~}A{~3~}..A{~n~}$}, vom considera un punct P arbitrar ales în plan. Vom "împărţi" poligonul în triunghiuri de forma $PA{~i~}A{~i+1~}$ (considerăm că $A{~1~} = A{~n+1~}$) şi vom calcula "aria cu semn" $T{~i~}$ a fiecărui triunghi (în formula ariei nu vom folosi funcţia de valoare absolută). Distingem în acest moment două cazuri:

Pentru a calcula aria unui poligon oarecare {$A{~1~}A{~2~}A{~3~}..A{~n~}$}, vom considera un punct P arbitrar ales în plan. Vom "împărţi" poligonul în triunghiuri de forma $PA{~i~}A{~i+1~}$ (considerăm că $A{~1~} = A{~n+1~}$) şi vom calcula "aria cu semn" $T{~i~}$ a fiecărui triunghi (în formula ariei nu vom folosi funcţia de valoare absolută). Distingem în acest moment două cazuri:

* Poligonul are vârfurile orientate trigonometric. Pentru fiecare latură "spre dreapta", aria $T{~i~}$ corespunzătoare va fi negativă, iar pentru fiecare latură "spre stânga", aria $T{~i~}$ corespunzătoare va fi pozitivă.
* Poligonul are vârfurile orientate antitrigonometric. Pentru fiecare latură "spre dreapta", aria $T{~i~}$ corespunzătoare va fi pozitivă, iar pentru fiecare latură "spre stânga", aria $T{~i~}$ corespunzătoare va fi negativă.

Această formulă reprezintă "aria cu semn" a poligonului (o arie pozitivă indică parcurgerea vârfurilor în ordine trigonometrică, iar o arie negativă, parcurgerea in ordine antitrigonometrică). O sursă care se bazează pe această soluţie obţine "100 puncte":job_detail/891309?action=view-source.

h2. Aplicaţii

h3. Aplicaţii

O primă aplicaţie ar fi coliniaritatea a $N$ puncte. Pentru ca $N$ puncte să fie coliniare, trebuie ca aria determinată de poligonul asociat acestora să fie $0$. O altă aplicaţie drăguţă este următoarea : dacă un punct se află în interiorul unui poligon convex. Soluţia presupune calcularea ariei cu semnn a triunghiurilor determinate de oricare $2$ puncte de pe acest poligon şi punctul căutat. Dacă toate ariile au acelasi semn $(+$ sau $-)$, atunci punctul se află în interiorul poligonului.

8748