Fişierul intrare/ieşire:	polig.in, polig.out	Sursă	Autumn Warmup 2007, Runda 3
Autor	Marius Dragus	Adăugată de	dragus marius •mariusdrg
Timp execuţie pe test	0.025 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Polig

Lui Lucy ii plac mult florile roz si poligoanele convexe. Asa ca avand multe gradini cu flori roz in ele ea vrea, calare pe unicornul ei, sa parcurga gradinile,nu neaparat pe toate, astfel incat sa vada in total numarul maxim de flori si sa se miste in forma de poligon convex, pornind din origine. Gradinile sunt puncte in plan. Iar ea incepe din origine.

Date de intrare

Pe prima linie a fisierului polig.in se gaseste n numarul de puncte, iar pe urmatoarele n linii trei numere intregi x, y, c reprezentand coordonatele si numarul de flori din punctul respectiv. 

Date de iesire

Pe un singur rand se va scrie solutia, costul maxim pentru poligonul convex cerut.

Restrictii

• -10000 ≤ x[i] ≤ 10000
• 0 ≤ y[i] ≤ 10000
• 1 ≤ n ≤ 100
• Poligonul trebuie sa fie convex si sa contina originea.
• Oricare trei puncte sunt necoliniare iar nu exista 2 puncte care cu originea sa fie coliniare.

Exemplu

Explicatie

Poligonul maxim se face folosind punctele 3, 5, 1, in aceasta ordine.

Cum se trimit solutii?