W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Dany jest -kąt wypukły (gdzie ) i jego różnych przekątnych, parami nie przecinających się wewnątrz wielokąta. (Jedynym wspólnym punktem dwóch różnych przekątnych może być tylko wierzchołek wielokąta.) Wierzchołki wielokąta są ponumerowane kolejno od do w kierunku przeciwnym do ruchu wskazówek zegara. Wszystkie przekątne dzielą na mniejsze wielokąty wypukłe o rozłącznych wnętrzach.
Cztery przekątne 1-8, 8-3, 3-1 i 3-6 dzielą wielokąt przedstawiony na poniższym rysunku na dwa czworokąty i trzy trójkąty.
Ułóż program, który:
W każdym wierszu standardowego wejścia są zapisane dwie liczby całkowite dodatnie oddzielone pojedynczym odstępem.
W pierwszym wierszu jest zapisana liczba wierzchołków wielokąta i liczba przekątnych .
W każdym z kolejnych wierszy znajduje się opis jednej przekątnej wielokąta w postaci pary liczb całkowitych dodatnich - numerów wierzchołków, które łączy ta przekątna; bezpośrednio po drugiej z liczb następuje koniec wiersza.
Dane w standardowym wejściu są zapisane poprawnie i Twój program nie musi tego sprawdzać.
W standardowym wyjściu należy zapisać jedną liczbę całkowitą dodatnią - maksymalną liczbę boków wielokąta wypukłego powstałego z podziału danego wielokąta .
Dla danych wejściowych:
9 4 1 8 8 3 3 1 3 6
poprawną odpowiedzią jest:
4
Autor zadania: Krzysztof Diks.