NézetNyomtat

Sokszög háromszögelése (Megoldás)
Címkék > Feladat

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.beharom.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