MaIn forum

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.