Do ASD jeszcze trochę czasu, ale można się rozerwać robiąc zadania :p 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.

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