Sokszög háromszögelése
Egy önmagát nem metsző, zárt töröttvonallal meghatározott sokszöget kell felbontanunk háromszögekre. A felbontáshoz az eredeti sokszög átlóit használhatjuk, de nem vehetünk fel új pontokat.
Bemenet
A csúcsok száma ($4\le N \le 1000$), majd a csúcsok koordinátái egy körüljárási irány szerint felsorolva ($-100\le x_i,y_i \le 100$).
Kimenet
A háromszögeléshez használt átlók száma, majd az átlók végpontjainak sorszáma
(az eredeti sorrend szerint, 1-től kezdődő indexeléssel).
Példa
| harom.be | harom.ki |
14 2 2 4 3 3 5 -1 6 -3 2 -2 -1 2 -2 8 2 6 2 2 0 -1 0 -2 2 -1 4 2 3 |
11 2 14 3 14 4 14 4 13 5 13 5 12 5 11 6 11 6 10 7 10 10 8 |