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
|
Tesztadatok
