Lekcja_12 - algorytmy w geometrii1. Algorytmy w geometriiWyjścieAlgorytmy w geometrii1. (1p) Niech będą trzy punkty a = (2,3), b = (3,-3), c = (-3,-2). Które zdanie jest prawdziwe? punkt (0,0) leży po prawej stronie prostej wyznaczonej przez wektor (a,c) punkt (0,1) leży po prawej stronie prostej wyznaczonej przez wektor (a,c) punkt (3,0) leży po prawej stronie prostej wyznaczonej przez wektor (b,a) 2. (1p) Niech Q będzie skończonym zbiorem punktów na płaszczyźnie. Przypuśćmy, że wszystkie punkty tego zbioru leżą na dwóch przecinających się prostych. Który z algorytmów wyszuka otoczkę wypukłą dla zbioru Q z mniejszym kosztem? Algorytm trójkątów Algorytm Grahama Algorytm Jarvisa3. (1p) Jaki byłby koszt algorytmu Grahama zastosowanego do zbioru n punktów, gdyby do sortowania tych punktów użyć algorytmu SelectionSort? rzędu n lg n rzędu n^2 rzędu n rzędu n ^3 4. (1p) Punkty (1,4), (2,5) i (3,6) są współliniowe. Prawda czy fałsz? prawda fałsz5. (1p) Ile wierzchołków będzie miała otoczka wypukła zbioru Q złożonego z 120 punktów, jeżeli wszystkie punkty leżą w równych odstępach na obwodzie koła o promieniu 10? 120/10 10 120 2406. (1p) Jakiej pomocniczej struktury danych używa algorytm Grahama? kolejek kolejek priorytetowych listy dwukierunkowej stosuOdpowiedzi :  Wyniki