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
Jak przetłumaczylibyście ten pseudokod na polski
Widziałem na ważniaku próbę tłumaczenia tego pseudokodu jednak moim zdaniem różni się ona nieznacznie
od tego co np w angielskiej wersji CLRS Intoduction to Algorithms którą podałem powyżej
Zadam wam cztery pytania jeśli na nie odpowiecie to łatwo zapiszecie powyższy pseudokod w ulubionym języku programowania
1. Jak wyszukać minimum ze względu na obydwie współrzędne
2. Kiedy punkt leży na prawo (bądź na lewo) wektora
3. Jak posortować punkty względem obydwu współrzędnych biegunowych
Tutaj wystarczy nam funkcja porównująca kąty oraz odległości punktu od bieguna (wcześniej wyszukanego minimum)
przy czym porównywanie kątów powinno być zrealizowane bez ich obliczania a porównywanie odległości bez wyciągania pierwiastka kwadratowego
Powinna ona zwracać wartość całkowitą podobnie jak strcmp dla łańcuchów
4. Jak usunąć punkty współliniowe
Tak właściwie to może lepiej je przenieść na koniec tablicy bądź listy
na wypadek gdybyśmy chcieli tę otoczkę narysować
Użytkownik Mariusz M edytował ten post 03.12.2019 - 18:20