Problema Poligon

Problema 2    Clasele IX-X (Echipe) 100 Puncte

Poligon

La ora de geometrie Grigorel a invatat despre poligoane si proprietatea acestora de a fi convexe. Deoarece il fascineaza matematica atat de mult, el incearca sa determine daca un poligon este convex sau nu fara sa-l deseneze, stiind doar coordonatele varfurilor acestuia. Grigorel nu se prea descurca si va roaga sa-l ajutati.

Cerinte:

Dandu-se un numar n de poligoane, se cere sa se determine pentru fiecare daca este convex sau nu. Daca poligonul este convex, sa se calculeze si aria sa.

Date de intrare: Datele se citesc din fisierul poligon.in astfel:

- pe prima linie numarul n de poligoane

- pentru fiecare poligon se citeste numarul m de varfuri, iar de pe urmatoarele m linii se citesc cate doua numere x si y, despartite prin spatiu, care reprezinta coordonatele unui varf. Varfurile sunt date parcurgand poligonul in ordine trigonometrica.

Date de iesire: Datele de iesire se vor tipari in fisierul poligon.out astfel:

- se vor afisa n linii, pe fiecare linie se va tipari aria poligonului (doar cu o zecimala) daca acesta este convex, sau valoarea 0 in caz contrar

Restrictii si precizari:

- 0<n<=10 si     2<m<=1000

- coordonatele sunt numere intregi din intervalul [-32 000 , 32 000]

- pentru 20% din teste se garanteaza 2<m<=10

- pentru 50% din teste se garanteaza 2<m<=50

Exemplu:

poligon.in poligon.out

4.0

0

Timp maxim de executie 1 secunda