Cześć wszystkim chciałbym się serdecznie przywitać i prosić o pomoc w rozwiązaniu zadania: (podaje link ponieważ treść jest długa) http://main.edu.pl/pl/archive/oi/6/olt
nie wiem jak zrobić wyszukiwanie drogi przez którą może przejść zły duch, myślę i nie mogę wpaść na nic sensownego, proszę o jakieś naprowadzenie.
Pozdrawiam
Zainteresuj się grafami i zaprzyjaźnij się z tą stroną: http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol008.php
Dziękuje zaczynam lekturę :)
naiwny algorytm wygląda tak. Liczysz wektory między środkiem danej świątyni, a rogami pozostałych świątyń.
Następnie sprawdzasz czy wyznaczane na tej podstawie łuki pokrywają pokrywają cały zakres łuku odpowiadający za wejście.
Złożoność obliczeniowa wychodzi o(n2).
Czyli zasadniczo zabawa w licznie iloczynów skalarnych i wektorowych dwóch wektorów.
Masz niebieskie książeczki na http://oi.edu.pl/ nie wiesz - czytasz.
Dziękuję za wszystkie odpowiedzi, piszę już kod może mi się uda to zrobić :)