== include(page="template/taskheader" task_id="gradina") ==

Poveste si cerinta...

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 inchise, iar interioarele lor vor reveni una lui Ion si cealalta 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.

h2. 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$}.

h2. Date de iesire

...

Pe prima linie a fisierului $gradina.in$ se afla un numar real, afisat cu o zecimala exacta, diferenta minima dintre ariile celor doua terenuri. Urmatoarea linie contine o distribuire a tarusilor. Astfel, ea va contine $N$ caractere. Daca al $i$-lea caracter

h2. Restrictii