Diferente pentru problema/triangulare intre reviziile #10 si #18

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="triangulare") ==
Petrica a trecut acum pe geometrie. Un poligon se numeste simplu daca poligonul nu se autointersecteaza sau, mai riguros, oricare doua laturi nu au in comun decat cel mult vârfurile acestuia. Orice poligon simplu cu $N$ varfuri poate fi triangulat, sau impartit in triunghiuri, prin trasarea a $N-3$ segmente intre varfurile acestuia, cu conditia ca aceste segmente, impreuna cu laturile poligonului nu se intersecteaza intre ele, cu exceptia varfurilor pe care le au in comun.
Petrica a trecut acum pe geometrie. Un poligon se numeste simplu daca poligonul nu se autointersecteaza sau, mai riguros, oricare doua laturi nu au in comun decat cel mult varfurile acestuia. Orice poligon simplu cu $N$ varfuri poate fi triangulat, sau impartit in triunghiuri, prin trasarea a $N - 3$ segmente intre varfurile acestuia, cu conditia ca aceste segmente, impreuna cu laturile poligonului nu se intersecteaza intre ele, cu exceptia varfurilor pe care le au in comun.
Pentru un poligon simplu dat, voi trebuie sa il triangulati.
h2. Restricţii
* $1 ≤ T ≤ 3$
* $T = 5$
* $4 ≤ N ≤ 50$
* Coordonatele sunt numere intregi din intervalul $[-10^3^, 10^3^]$
* Indicii sunt numerotati de la $0$.
* **ATENTIE!** In caz ca exista mai multe triangulari, se va afisa triangularea care da lista minima lexicografica. De exemplu, daca o triangulare valida da lista $0 2, 0 3, 2 4$ iar o a doua triangulare valida este lista $0 2, 0 4, 1 3$ atunci se va afisa prima deoarece este mai mica lexicografica.
h2. Exemplu
table(example). |_. triangulare.in |_. triangulare.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 3
  4
  0 0
  5 0
  5 5
  0 5
  4
  0 0
  5 0
  5 5
  3 2
  5
  0 5
  3 2
  5 5
  5 0
  0 0
| 0 2
  1 3
  1 3
  1 4
|
h3. Explicaţie
...
Pentru primul test se observa ca avem un patrat, si orice diagonala a sa este buna, dar o alegem pe cea care ne ofera minimul lexicografic, adica segmentul $0 2$. In cazul celui de-al doilea test deoarece poligonul nu mai este un patrat, singura solutie posibila este segmentul $1 3$. Raspunsul pentru ultimul test este din nou unic, iar lista este formata din segmentele $1 3$ si $1 4$.
== include(page="template/taskfooter" task_id="triangulare") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
9418