Olimpiada Judeteană de Informatică
9 martie 2002, ora 9
00

CLASA a X-a

PROBLEMA 1 (Triang)

Document Microsoft Word

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