Diferente pentru problema/gradina intre reviziile #3 si #12

Diferente intre titluri:

gradina
Gradina

Diferente intre continut:

== include(page="template/taskheader" task_id="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 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.
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.
h2. Date de intrare
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 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.
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.
h2. Restrictii
* $6 ≤ N ≤ 400$
* $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.
h2. Exemplu
table(example). |_. gradina.in |_. gradina.out |
|6
|?
?
|7
0 0
2 0
1 4
4 5
0 2
2 2
4 3
|1.0
IIVVIIV
|
h3. Explicatie
== include(page="template/taskfooter" task_id="gradina") ==
...
== include(page="template/taskfooter" task_id="gradina") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
1958