Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie
        LICEUM        

Otoczka wypukła



  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
Brak odpowiedzi do tego tematu

#1 Mariusz M

Mariusz M

    Wielki Analityk

  • Użytkownik
  • Redaktor
  • 901 postów
414
Instruktor II
  • Płeć:Mężczyzna

Napisano 20.09.2017 - 10:20

	
		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

  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55