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.
Powiemy, że dwa trójkąty przecinają się, jeśli ich wnętrza mają co najmniej jeden wspólny punkt. Wielokąt jest wypukły, jeśli każdy odcinek łączący dowolne dwa punkty tego wielokąta jest w nim zawarty. Trójkątem elementarnym w wielokącie wypukłym nazywamy każdy trójkąt, którego wierzchołki są wierzchołkami tego wielokąta. Triangulacją wielokąta wypukłego nazywamy każdy zbiór elementarnych trójkątów w tym wielokącie, w którym żadne dwa trójkąty nie przecinają się, a wszystkie razem pokrywają cały wielokąt.
Dane są wielokąt i jego triangulacja. Jaka jest największa liczba trójkątów w tej triangulacji, które może przeciąć jeden elementarny trójkąt w tym wielokącie?
Rozważmy następującą triangulację:
Trójkąt elementarny przecina wszystkie trójkąty w tej triangulacji.
Napisz program, który:
Pierwszy wiersz standardowego wejścia zawiera liczbę , . Jest to liczba wierzchołków wielokąta. Wierzchołki wielokąta są ponumerowane kolejno , zgodnie z ruchem wskazówek zegara.
Kolejne wiersze zawierają opisy trójkątów w triangulacji. W wierszu , , zapisane są trzy liczby całkowite , oddzielone pojedynczymi odstępami. Są to numery wierzchołków -tego trójkąta w triangulacji.
W pierwszym i jedynym wierszu standardowego wyjścia należy zapisać jedyną liczbę całkowitą — największą liczbę trójkątów w triangulacji, które przecina jeden elementarny trójkąt w wielokącie wejściowym.
Dla danych wejściowych:
6 0 1 2 2 4 3 4 2 0 0 5 4
poprawną odpowiedzią jest:
4
Autor zadania: Krzysztof Diks.