Niezrozumiałe treści zadań algorytmicznych

[Exigo]

Hej. Dostałem serię zadań, z czego dwa posiadają treść nic nie mówiącą. W większości przypadków jest opisana implementacja, te zaś pozostają zagadką. Żadnych źródeł czy wskazówek. Oto one:

1. Algorytm wyszukiwania krawędzi dowolnego wielokąta wypukłego.

2. Algorytm wyszukiwania wierzchołków wielokąta foremnego poprzez odrzucenie punktów skrajnych.

Przychodzą komuś do głowy jakieś słowa-klucze, metody? Będę wdzięczny za wszelkie pomysły. :)

(z początku myślałem że chodzi o otoczkę Grahama, lecz ta odpada ponieważ jest to zawarta w dalszych zadaniach)

[Grela]

Czytaj ze zrozumieniem ;). To tyle odemnie.

 

Tylko proszę nie mów mi, że nie wiesz co to wielokąt wypukły albo punkty skrajne, bo bez tego ani rusz. A jak wiadomo programowanie to w 99% matma :thumbsup:

 

I po co Ci implementacja skoro te zadania wymagają tego, żebyś sam się domyślił jak napisać taki algorytm korzystając z własnej wiedzy.

[kt1117]

Ale tu przecież brak jakiejkolwiek specyfikacji i skąd wiadomo co zrobić jak nie ma podanych przykładów wejścia/wyjścia.

E:Jeżeli dostałbym tablicę bool'ów NxM to jechałbym wierszami i szukał 1, gdy znajdę, zapisałbym w tablicy współrzędne poczym zacząłbym szukać 0. I znowu zapisał w tablicy,ale na sam koniec.

Tak uzyskałbym listę wszystkich pkt. znajdujących się na krawędziach. Następnie wczytałbym 1 pkt. z listy i zapisał do drugiej listy, bo na pewno jest wierzchołkiem. Odjąłbym jego współrzędne od współrzędnych nast. i uzyskałbym coś jakby wektor 2d kierunku krawędzi. Jechałbym tak po liście aż wektor zmieni wartość i współrzędną tego pkt. przepisałbym do tej 2 listy co ostatnio. Po przejściu przez listę otrzymamy listę ze wszystkimi wierzchołkami. Problem może być z płaskimi fragmentami, ale można chyba łatwo obracać macierze także można wykonać skrypt, przechylić macierz o np. 45 deg. wykonać skrypt krawędzi ponownie i obrócić nowe wynikowe krawędzie o 45 deg. w drugą stronę. Na koniec dodać do siebie te listy z krawędziami i powinno grać i hulać.