Точка и треугольник
Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?
Входные данные
Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.
Выходные данные
Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.
| № | Входные данные | Выходные данные |
|---|---|---|
| 1 | 2 6 -9 3 8 1 5 11 | 1 |
| 2 | -13 10 -12 5 99 80 17 13 | 0 |
| 3 | 98 -50 -87 7 5 3 23 17 | 0 |
| 4 | 5 15 7 12 5 3 2 54 | 1 |
| 5 | 2 2 3 1 1 3 9 11 | 1 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> using namespace std; int main() { double x0,x1,x2,x3,y0,y1,y2,y3; double z1,z2,z3; cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3; z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0); z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0); z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0); if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) cout<<"1"; else cout<<"0"; return 0; } |
Решение
Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.
Ссылки
Ссылка на Ideone
Ссылка на e-olymp
One thought on “e-olymp 143. Точка и треугольник”