Pagini recente » zeroc | Diferente pentru problema/mmo intre reviziile 5 si 26 | Atasamentele paginii Joc5 | Diferente pentru algoritmiada-2013/runda-4/open intre reviziile 2 si 3 | Diferente pentru problema/poligon7 intre reviziile 3 si 2

Diferente pentru problema/poligon7 intre reviziile #3 si #2

Diferente intre #3 si #4

Diferente intre #1 si #2

Nu exista diferente intre titluri.

Diferente intre continut:

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

Se consideră un poligon convex cu N laturi. Se vor efectua N - 1 mutări. O mutare constă în alegerea a două puncte A și B vecine pe poligon și mutarea punctului A în B (vezi figura). Costul mutării este egal cu distanța euclidiană dintre A și B. După mutare punctul A este asimilat de B, iar procesul se reia pe noul poligon. Se cere costul total minim al unei succesiuni de N - 1 mutări care reduce poligonul la un singur punct, precum și o modalitate de a obține acest cost.

Se consideră un poligon convex cu N laturi. Se vor
efectua N - 1 mutări. O mutare constă în alegerea a
două puncte A și B vecine pe poligon și mutarea
punctului A în B (vezi figura). Costul mutării este
egal cu distanța euclidiană dintre A și B. După
mutare punctul A este asimilat de B, iar procesul se
reia pe noul poligon. Se cere costul total minim al unei succesiuni de N - 1 mutări care reduce poligonul la un singur punct, precum și o modalitate de a obține acest cost.

h2. Cerinţe
Dându-se T poligoane convexe, să se determine:
1. Costul minim ans al unei succesiuni de mutări care reduce poligonul la un singur punct;
2. O succesiune de mutări de cost minim.

h2. Date de intrare
Fișierul de intrare poligon.in conține pe prima linie un număr întreg p, reprezentând numărul cerinței ce

- pe prima linie numărul natural N, reprezentând numărul de laturi ale poligonului;
- pe următoarele N linii câte 2 numere întregi x și y, separate printr-un spațiu, reprezentând
coordonatele vârfurilor poligonului curent, Vârfurile sunt date în ordine trigonometrică.

h2. Date de ieşire
Fișierul de ieșire poligon.out va conține, în funcție de valoarea lui p, următoarele informații:
1. Dacă p = 1 se rezolvă doar cerința 1. Pentru fiecare dintre cele T teste se va afișa câte un număr real ans pe o linie, cu semnificația din enunț.
2. Dacă p = 2 se rezolvă doar cerința 2. Pentru fiecare din cele T teste se vor afișa câte N-1 linii, fiecare dintre aceste fiind de forma A B, reprezentând mutările în ordinea în care acestea se efectuează.

h2. Restricţii și precizări
• 1≤T≤5

infoarena informatica de performanta

Diferente pentru problema/poligon7 intre reviziile #3 si #2

Nu exista diferente intre titluri.

Diferente intre continut:

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.