Fişierul intrare/ieşire:	gradina.in, gradina.out	Sursă	preONI 2007 Runda Finala
Autor	Filip Cristian Buruiana	Adăugată de	Filip Cristian Buruiana •filipb
Timp execuţie pe test	0.7 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Gradina

Ion si Vasile sunt doi ciobani mioritici. De-alungul timpului, cand erau prieteni, ei au infipt in terenul de la marginea satului N tarusi. Daca consideram acest teren ca fiind plan, atunci tarusii pot fi considerati puncte laticiale ( puncte de coordonate intregi ). Dupa ce s-au certat, cei doi s-au decis sa isi imparta terenul. Pentru aceasta, fiecare tarus trebuie atribuit fie lui Ion, fie lui Vasile. Tarusii formeaza astfel 2 poligoane, iar interioarele lor ( impreuna cu zona de frontiera ) vor reveni unul lui Ion si celalalt lui Vasile. Evident, cele doua regiuni care revin ciobanilor nu trebuie sa aiba nici macar un punct in comun, altfel ar putea aparea noi conflicte. Mai mult, cele doua regiuni trebuie sa aiba forma de poligon convex.
Dandu-se cei N tarusi, sa se determine o modalitate de distribuire a lor astfel incat diferenta dintre aria celor doua terenuri care se formeaza sa fie minim posibila si toate conditiile impuse mai sus sa fie respectate.

Date de intrare

Pe prima linie a fisierului gradina.in se afla N, numarul de tarusi. Fiecare din urmatoarele N linii contine o pereche de numere intregi x y, reprezentand coordonatele unui tarus. Toate coordonatele sunt, in modul, mai mici sau egale cu 50 000 000.

Date de iesire

Pe prima linie a fisierului gradina.out se afla un numar real, afisat cu o zecimala exacta, diferenta minima dintre ariile celor doua terenuri. Urmatoarea linie contine o distribuire a tarusilor pentru care se obtine diferenta minima. Astfel, ea va contine N caractere. Daca al i-lea caracter este I, atunci tarusul al i-lea din fisierul de intrare ii este asociat lui Ion. Daca caracterul este V, atunci tarusul va fi atribuit lui Vasile.

Restrictii

• 6 ≤ N ≤ 250
• Oricare 3 puncte din cele N nu sunt coliniare
• Daca exista mai multe distribuiri ale tarusilor pentru care se obtine aceeasi diferenta minima, se va afisa cea minim lexicografica
• Cele doua regiuni nu vor contine un tarus in interiorul lor.

Exemplu

Cum se trimit solutii?