Otoczka wypukla

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Robakks
Czasem tu bywam
Czasem tu bywam
Posty: 126
Rejestracja: 30 wrz 2012, 20:36
Podziękowania: 2 razy
Otrzymane podziękowania: 10 razy
Płeć:

Otoczka wypukla

Post autor: Robakks » 18 sie 2017, 00:17

Znalazlem u Cormena taki pseudokod

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
Jak ten pseudokod zapisac w jezyku programowania

Robakks
Czasem tu bywam
Czasem tu bywam
Posty: 126
Rejestracja: 30 wrz 2012, 20:36
Podziękowania: 2 razy
Otrzymane podziękowania: 10 razy
Płeć:

Post autor: Robakks » 01 paź 2017, 13:22

Znalazłem w książce Sedgewicka kod takiej funkcji

Kod: Zaznacz cały

int ccw (struct point p0,
            struct point p1,
            struct point p2)
    {
            int dx1,dx2,dy1,dy2;
            dx1 = p1.x - p0.x; dy1 = p1.y-p0.y;
            dx2 = p2.x - p0.x; dy2 = p2.y-p0.y;
            if (dx1*dy2 > dy1*dx2)  return 1;
            if (dx1*dy2 < dy1*dx2)  return -1;
            if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1;
            if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2))  return 1;

            return 0;
    }
Czy można użyć tej funkcji do porównywania podczas sortowania oraz sprawdzania warunku dla pętli
while z kroku 8 tzn czy porównywananie z użyciem tej funkcji będzie dawało poprawne wyniki

Załóżmy że uprzemy się na przechowywanie punktów w tablicy zamiast na liście
i zrezygnujemy z usuwania punktów współliniowych w kroku drugim algorytmu
Jak zmodyfikować pseudokod Cormena aby algorytm zatrzymywał się zwracając poprawny wynik