Olimpiada Jude
teană de InformaticăCLASA a X-a
PROBLEMA 1 (Triang)
O triangulatie a unui poligon convex este o multime formată din diagonale ale poligonului care nu se intersectează în interiorul poligonului ci numai în vârfuri si care împart toată suprafata poligonului în triunghiuri.
Fiind dat un poligon cu n vârfuri notate 1, 2, ..., n
să se genereze toate triangulatiile distincte ale poligonului. Două triangulatii sunt distincte dacă diferă prin cel putin o diagonală.Date de intrare:
în fisierul text TRIANG.IN se află pe prima linie un singur număr natural reprezentând valoarea lui n (n£ 11).Date de iesire:
în fisierul text TRIANG.OUT se vor scrie:– pe prima linie, numărul de triangulatii distincte;
– pe fiecare din următoarele linii câte o triangulatie descrisă prin diagonalele ce o compun. O diagonală va fi precizată prin două numere reprezentând cele două vârfuri care o definesc; cele două numere ce definesc o diagonală se despart prin cel putin un spatiu, iar între perechile de numere ce reprezintă diagonalele dintr-o triangulatie se va lăsa de asemenea minimum un spatiu.
Exemplu:
TRIANG.IN
5
TRIANG.OUT
5
1 3 1 4
2 4 2 5
5 2 5 3
3 5 3 1
4 2 1 4
Timp maxim de executare:
7 secunde/test pe un calculator la 133 MHz.
3 secunde/test pe un calculator la peste 500 MHz.
Închideti fereastra curentă pentru revenire