to odpowiedz na kilka pytań
Kod: Zaznacz cały
GRAHAM-SCAN(Q)
1 let p0 be the point in Q with the minimum y-coordinate,
or the leftmost such point in case of a tie
2 let <p1,p2,...,pm> be the remaining points in Q,
sorted by polar angle in counterclockwise order around p0
(if more than one point has the same angle, remove all but
the one that is farthest from p0)
3 let S be an empty stack
4 PUSH(p0,S)
5 PUSH(p1,S)
6 PUSH(p2,S)
7 for i=3 to m
8 while the angle formed by points NEXT-TO-TOP(S), TOP(S), and pi makes a nonleft turn
9 POP(S)
10 PUSH(pi,S)
11 return S
Krok pierwszy zrealizowałbym w dwóch pętlach gdzie pierwsza znajduje punkt o najmniejszej
współrzędnej rzędnej a druga znajduje wśród punktów o najmniejszej rzędnej najmnieszą odciętą
Ciekawy jestem czy można zrealizować to w jednej pętli i jeśli tak to jak
Jeśli chodzi o krok drugi to wygląda na to że trzeba posortować punkty jednocześnie ze względu na
obydwie współrzędne biegunowe
(ze względu na argumenty zespolone rosnąco ze względu na moduły malejąco)
Chociaż jeśli chodzi o moduły to można się ograniczyć do znajdowania maximum
Dla listy widziałem procedurę sortującą przez scalanie ale tylko względem jednego klucza jednocześnie
Widziałem też procedurę usuwającą duplikaty z listy posortowanej co może być przydatne
Jak zrealizować warunek dla pętli while z kroku ósmego?
Czy tutaj przydatny będzie wyznacznik ?
Aby uniknąć arytmetyki zmiennoprzecinkowej można rozpatrywać kwadrat modułu
ale co z argumentem liczby zespolonej , jak go przechowywac ?
Czy program napisany na podstawie powyższego pseudokodu znalezionego u Cormena i reszty
będzie działał dla każdych danych wejściowych ?
Kod z książki Sedgewicka działał tylko dla niektórych danych wejściowych
Sprawdzałem tylko algorytm Jarvisa