Forum matematyczno-informatyczne
Do ASD jeszcze trochę czasu, ale można się rozerwać robiąc zadania A że znalazłem takie dość ciekawe, to zamieszczę, do zastanowienia w długie zimowe wieczory (albo w przypadku niektórych - przez pięć minut):
1. (egzamin 2003, zadanie 4)
Na płaszczyźnie dodajemy kolejno punkty o współrzędnych (x_i, y_i) takie, że x_(i+1) > x_i. Po dodaniu kolejnego punktu łączymy go ze wszystkimi wcześniejszymi punktami takimi, że żadne odcinki się nie przetną. Definiujemy funkcje
Liczba - zwraca liczbę dotychczas utworzonych krawędzi
Obwód - zwraca liczbę krawędzi na obwodzie figury powstałej w wyniku dodawania kolejnych punktów.
Zaproponuj strukturę danych, która umożliwia dodawanie nowych punktów i obliczanie podanych funkcji w zamortyzowanym czasie stałym.
Offline
I jeszcze obrazek na potwierdzenie oczywistego faktu, że możemy dodawać liniowo wiele krawędzi:
http://students.mimuw.edu.pl/~sr248277/ … anie-1.gif
Cyferki oznaczają obwód po umieszczeniu punktu w danym regionie
Offline