Obliczanie kąta pomiędzy trzema punktami - Zadanie Autobus OIG

Question

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ę.

Comments

Wiem, że nie jest to jakiś trudny problem, ale jakimś orłem z geometri to (jeszcze!) narazie nie jestem.

---

Klasyczne rozwiązanie trójkąta, są do tego gotowe wzory, ale można też na piechote dzieląc dany trójkąt na dwa trójkąty prostokątne.

---

@Oscar, 

Ukryłem ten mój przedchwilą komentarz, bo było to lekkie nieporozumienie.

Ale w sensie; jak podzielę to na 2 trójkąty prostokątne, to P = a * h / 2, P wylicze z wzoru Herona, co dalej?

---

Dobra, jestem kompletnym debilem. Poprostu P = A * H / 2, z wzoru Herona obliczam pole, A znam więc elo, drugi bok liczę z Pitagorasa, więc mam sinusa i koniec. Sory za tak głupie pytanie i stracony czas.

Answer 1

Można też obliczyć sam kąt - jeśli wyznaczyć równania prostych P1-P2 i P2-P3 to współczynnik a we wzorze to y=ax+b to tangens kąta nachylania prostej - różnica kątów nachylenia oby prostych da szukany kąt. Oczywiście ten wzór wysiada dla prostych pionowych - działa wtedy bardziej uniwersalne równanie prostej aX+bY+c = 0, i a/b to ten tangens. W bibliotekach różnych języków jest funkcja atan2(y,x) - to taki odpowiednik arcus tangens dla przypadku gdy dany jest odcinkek <X, Y> i to działa nawet gdy Y=0 i działa w całym zakresie 0-360 stopni.

W sumie dostaje się wzór postaci atan2(p1.y-p2.y, p1.x-p2.x)-atan2(p2.y-p3.y, p2.x-p3.x). Być może kolejność odejmowania należy dobrać. Oczywiście wyjdzie w radianach.

Comments

Też tak  podszedłbym do tego problemu.

---

@Oscar, 

to wsumie, będzie nawet lepsze niż moje, bo ja mam dużo wyliczeń, a w tym to poprostu kilka linijek i już.

---

Panowie, wystarczy utworzyć dwa wektory i skorzystać z iloczynu skalarnego :)