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.