Wielokąt
Limit pamięci: 32 MB
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?
Przykład
Rozważmy następującą triangulację:
Trójkąt elementarny przecina wszystkie trójkąty w tej triangulacji.
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia liczbę wierzchołków wielokąta i jego triangulację;
- oblicza największą liczbę trójkątów, które przecina pojedynczy elementarny trójkąt w danym wielokącie;
- zapisuje wynik na standardowe wyjście.
Wejście
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.
Wyjście
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.
Przykład
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.