Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-06-21 12:26:06.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:gradina.in, gradina.outSursăpreONI 2007 Runda Finala
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.7 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 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.

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.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

Restrictii

  • ... ≤ ... ≤ ...

Exemplu

gradina.ingradina.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicatie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?