zadanie dla fil geometria obliczeniowa Mariusz: https://prnt.sc/st3m6x Jak napisałbyś program do znajdowania otoczki wypukłej korzystając z wyżej wymienionego algorytmu Sugerowana struktura danych to dwukierunkowa lista cykliczna

fil: Czesc Mariusz, moge cos napisac zaraz, bo pamietam ze kiedys ten temat przerabialem, ale nie udalo mi sie skleic dzialajacego programu. Wspolrzedne punktu przyjmujemy jako inty?

fil: "sorted by polar angle in counterclockwise order around p₀" − czyli wedlug czego mam posortowac?

fil: Podrzucam kod − udalo mi sie napisac https://pastebin.com/ra8cHmi3

Mariusz: Na wektorze to pewnie i ja wygrzebałbym jakiś kod według miary kąta nachylenia do osi OX przeciwnie do ruchu wskazówek zegara Jeśli miałeś układ biegunowy to jest to miara kąta nachylenia promienia wodzącego do osi biegunowej Gdy poznasz liczby zespolone to dowiesz się że ten kąt to argument liczby zespolonej https://pastebin.com/07r6DwmV No ja napisałem coś takiego z bardzo małą pomocą Pytającego a ty chyba wziąłeś kod od geeksów Masz jakiś pomysł na takie zmodyfikowanie kodu aby usunięte punkty współliniowe były umieszczane na końcu wektora

fil: https://www.geeksforgeeks.org/orientation-3-ordered-points/ Ten wzor bralem z geeksow

fil: Nawet widze ze kod mozna troche zmodyfikowac, pozbyc sie zmiennej globalnej, do funkcji compare() dodac trzeci argument − wtedy fragment kodu by tak wygladal std::sort(points.begin() + 1, points.end(), [&start](auto first_point, auto second_point) { return compare(start, first_point, second_point); });

fil: Wlasnie ten algorytm co podeslales, znalazlem taki sam ale w polskiej wersjii. Do ktorego vectora dodawac te usuniete elementy?

fil: https://www.youtube.com/watch?v=iURPY28jOD4 −−− tutaj koles tez pokazuje tylko ten algorytm w 5:20. Tez z miesiac temu rozmawialem z wykladowca informatyki na politechnice krakowskiej o tym algorytmie

fil: Tez widze ze napiaslem recznie sortowanie

fil: Tutaj tez jest fajnie opisany ten algorytm: http://www.algorytm.org/geometria-obliczeniowa/znajdowanie-wypuklej-otoczki-algorytm-grahama.html

Mariusz: Chodzi o to że teraz funkcja int removeDup(std::vector<Point> &A); nadpisuje punkty współliniowe i zwraca liczbę punktów Chodzi o to aby nadpisane punkty umieścić w wektorze na pozycjach prev+1,...,size−1

fil: rozumiem ze direction(...) != 0 sprawdza czy 3 punkty sa wspoliniowe?

Mariusz: Widziałeś ten algorytm ? https://www.youtube.com/watch?v=kdAiCZQVuvI Punkty są współliniowe gdy direction(...) == 0

fil: jedyne co teraz na szybko przychodzi do glowy to miec jakas zmienna pomocnicza int k = 0 for (...; i < points.size() − k;...) if (...) { ... points.push_back(..); k++; } N aszybko, nie mam gwarancji ze bedzie poprawnie dzialac. Juz pozno jest, moze cos rano wymysle

fil: Poczekaj, te "niechciane" elementy sa nadal w tej tablicy, to jutro poprawie

Mariusz: Poza tym sugerowana była inna struktura danych np Diks i Rytter proponują dwukierunkową listę cykliczną Na wektorze napisałbym na podstawie pseudokodu Cormena przy niewielkiej pomocy Pytającego

fil: Przy okazji −− znasz jakies strony gdzie moge sobie pocwiczyc algorytmike/rozwiazywanie problemow −− oczywiscie angielskie. Project Eulera juz znam

Mariusz: Jeśli chodzi o otoczkę to widziałeś te kody ? https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain Ciekawy jestem jak przepisać ten algorytm tak aby punkty przechowywane były na liście dwukierunkowej

Mariusz: https://pastebin.com/fhgu9yS8 W liniach nr 40 oraz nr 46 ten pierwszy warunek dla pętli while mi przeszkadza aby przepisać kod z użyciem listy dwukierunkowej

zadanko: fil,polecam hackerrank,angielski spoj,oraz codewars