Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/mVAfHT3mw6IurviIcUJCnivk/site/?key=statement
Wydaje się nie być ono jakieś bardzo trudne, poprostu puszczam Dijkstrę, ale cały problem polega na tym, że droga pomiędzy dwoma punktami nie może być > 90 stopni. I mam problem, jak obliczyć kąt pomiędy 3 odcinkami, w sensie nawet nie muszę go liczyć, ale sprawdzić czy jest <= 90 stopni.
Myślałem, żeby narysować ala równoległobok i spuścić wysokość i podstawić do wzoru na pole trójkąta z sinusem, i też porównać do pola trójkąta z wzoru Herona. Nwm czy to jest dobre i wgl bardzo dużo wyliczeń, a może da się jakoś łatwiej to wyliczyć.
Rysunek poglądowy co chcę wyliczyć, znając współrzędne 3 punktów:
Jak będę wiedział, jak wyliczyć taki kąt / czy jest <= 90 stopni, znając współrzędne P1, P2, P3, to reszta zadania wydaje się nie być trudna. Puszczam zwykłą Dijkstrę.