Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | triangulare.in, triangulare.out | Sursă | ONIS 2014, Runda 1 |
| Autor | Dragos Oprica | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
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.
Pentru un poligon simplu dat, voi trebuie sa il triangulati.
Date de intrare
Fişierul de intrare triangulare.in contine pe prima linie un numar natural T reprezentand numarul de teste. Fiecare test va avea pe prima linie a sa un numar natural N reprezentand numarul de varfuri ale poligonului. Pe urmatoarele N linii se afla cate doua numere intregi, x si y, reprezentand coordonatele punctelor. Coordonatele poligonului sunt date in sens trigonometric.
Date de ieşire
În fişierul de ieşire triangulare.out se vor afisa raspunsurile pentru cele T teste. Un test este format din N - 3 linii, pe fiecare linie fiind doua numere, a si b reprezentand indicii celor doua varfuri care formeaza segmentul respectiv. Lista segmentelor trebuie sa fie sortata crescator dupa valoarea a, iar in caz de egalitate crescator dupa valoarea b.
Restricţii
- 1 ≤ T ≤ 3
- Indicii sunt numerotati de la 0.
- ATENTIE! In caz ca exista mai multe triangulari, se va afisa triangularea care da lista minima lexicografica.
Exemplu
| triangulare.in | triangulare.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
