Polish version    English version  
  Historia OI -> V OI 1997/1998 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Terminarz
Statystyki
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
V Olimpiada Informatyczna 1995/96

Zadanie: WIE
Autor: Krzysztof Diks
Wielokąt

Zawody I stopnia  
Plik źródłowy: WIE.??? (np. pas, c, cpp)
Plik wykonywalny: WIE.exe
Plik wejściowy: WIE.in
Plik wyjściowy: WIE.out

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 (1,3,5) przecina wszystkie trójkąty w tej triangulacji.

Zadanie
Napisz program, który:

  • wczytuje z pliku tekstowego WIE.IN 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 w pliku tekstowym WIE.OUT

Wejście
Pierwszy wiersz pliku WIE.IN zawiera liczbę n, 3<=n<=1000. Jest to liczba wierzchołków wielokąta. Wierzchołki wielokąta są ponumerowane kolejno 0,1,...,n-1, zgodnie z ruchem wskazówek zegara. Kolejne n-2 wiersze zawierają opisy trójkątów w triangulacji. W wierszu i+1, 1<=i<=n-2, zapisane są trzy liczby całkowite a, b, c, oddzielone pojedynczymi odstępami. Są to numery wierzchołków i-tego trójkąta w triangulacji.

Wyjście
W pierwszym i jedynym wierszu pliku WIE.OUT 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 pliku wejściowego WIE.IN:

6
0 1 2
2 4 3
0 5 4
2 4 0
poprawnym rozwiązaniem jest plik tekstowy WIE.OUT:
4

Twój program powinien szukać pliku WIE.IN w katalogu bieżącym i tworzyć plik WIE.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę WIE.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku WIE.EXE





Wersja do druku