IV Olimpiada Informatyczna 1996/97
|
Zadanie: TRO
|
Autor: Wojciech Guzicki
|
Zawody III stopnia |
Plik źródłowy: | TRO.??? (np. pas, c, cpp) |
Plik wykonywalny: | TRO.exe |
Plik wejściowy: | TRO.in |
Plik wyjściowy: | TRO.out |
W przestrzeni rozmieszczono n punktów w taki sposób, że żadne trzy z nich nie są współliniowe. Następnie każdą parę tych punktów połączono odcinkiem i każdy odcinek pokolorowano na czarno albo na czerwono. Trójkątem jednobarwnym nazwiemy każdy trójkąt mający wszystkie trzy boki tego samego koloru. Mamy daną listę wszystkich czerwonych odcinków. Chcemy znaleźć liczbę wszystkich trójkątów jednobarwnych.
W drugim wierszu pliku tekstowego TRO.IN jest zapisana jedna liczba całkowita m spełniająca nierówności 0 <= m <= 250000. Jest to liczba odcinków czerwonych.
W każdym z kolejnych m wierszy są zapisane dwie liczby całkowite p oraz k, oddzielone pojedyńczym odstępem i spełniające nierówność: 1 <= p < k <= n. Są to numery wierzchołków będących końcami kolejnego odcinka czerwonego.
6 9 1 2 2 3 2 5 1 4 1 6 3 4 4 5 5 6 3 6poprawnym rozwiązaniem jest plik tekstowy TRO.OUT
2
Twój program powinien szukać pliku TRO.IN w katalogu bieżącym i tworzyć plik TRO.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę TRO.???, 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 TRO.EXE.