Lista 3, Politechnika Opolska, Smolczyk, Zaawansowane algorytmy i struktury danych, Ćwiczenia
[ Pobierz całość w formacie PDF ]
Zaawansowane Algorytmy i Struktury Danych – lista 3
1.
Podać algorytm sprawdzający, czy dwa odcinki
p
1
p
2
i
p
3
p
4
mają punkty wspólne.
2.
Pokazać, jak sprawdzić, czy w zbiorze
n
punktów są trzy punkty współliniowe (można
to zrobić w czasie O(
n
2
lg
n
)).
3.
Podać algorytm (np. w postaci pseudokodu) sortowania ciągu
n
punktów <
p
1
,
p
2
, …,
p
n
> względem ich współrzędnych kątowych w biegunowym układzie współrzędnych o
początku w danym punkcie
p
0
.
4.
Podać algorytm obliczania pola wielokąta (niekoniecznie wypukłego) o
n
wierzchołkach (można to zrobić w czasie (
n
)).
5.
Podaj algorytm sprawdzający, czy
n
-wierzchołkowy wielokąt jest prosty, tzn. czy
tylko sąsiadujące krawędzie mają punkt wspólny (będący wierzchołkiem wielokąta).
[ Pobierz całość w formacie PDF ]