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. Ea cunoaste locatia a N gradini (gradinele sunt reprezentate ca puncte in plan) ce contin multe flori roz si isi doreste ca mergand calare pe unicornul ei, sa viziteze unele din gradini astfel incat sa vada in total numarul maxim de flori. Intre oricare doua gradini exista un singur drum direct format din segmentul ce le uneste. O alta dorinta a ei este ca traseul parcurs sa aiba forma unui poligon convex. Ea va porni tot timpul de la casa ei situata in originea planului (coordonata 0, 0). Determinati numarul maxim de flori ce il poate vedea.

Date de intrare

Pe prima linie a fisierului de intrare polig.in se afla N avand semnificatia din enunt, iar pe urmatoarele N linii trei numere intregi x, y si c reprezentand coordonatele si numarul de flori din gradina i-1.

Date de iesire

Pe prima linie a fisierului polig.out se afla un singur numar, numarul maxim de flori ce il poate vedea.

Restrictii si precizari

• 1 ≤ N ≤ 100
• -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?