Принадлежит ли точка О треугольнику
ABC? Точка
принадлежит треугольнику, если она лежит внутри его или на его границе.
Вход. Содержит
координаты точек O, A, B, C. Числовые значения не превышают по модулю 100.
Выход. Вывести
1, если точка O принадлежит треугольнику ABC и 0 в противоположном случае.
Пример входа 1 |
Пример выхода 1 |
1 1 -1 0 2 4 4 1 |
1 |
|
|
Пример входа 2 |
Пример выхода 2 |
-2 0 7 0 -2 5 0 -5 |
0 |
геометрия
Точка О
лежит внутри треугольника ABC, если все три поворота OAB, OBC, OCA одновременно
левые или правые.
Пример
В первом тесте точка (1, 1) лежит внутри треугольника.
Реализация алгоритма
Функция vect вычисляет векторное (косое)
произведение векторов a(x1, y1) и b(x2, y2) по формуле:
a ´ b = = x1 y2 – x2 y1
int vect(int x1, int y1, int x2, int y2)
{
return x1 * y2 - y1 * x2;
}
Читаем
входные данные.
scanf("%d %d %d %d %d %d %d %d",&xo,&yo,&xa,&ya,&xb,&yb,&xc,&yc);
Вычисляем косые произведения.
p = vect(xa - xo, ya - yo, xb - xa, yb -
ya);
q = vect(xb - xo, yb - yo, xc - xb, yc -
yb);
r = vect(xc - xo, yc - yo, xa - xc, ya -
yc);
Если все повороты имеют один знак, то точка О лежит
внутри треугольника.
if ((p <= 0 && q <= 0 && r <= 0) || (p
>= 0 && q >= 0 && r >= 0))
printf("1\n");
else printf("0\n");
Реализация алгоритма – 2
Читаем
входные данные.
scanf("%d %d %d %d %d %d %d %d",&xo,&yo,&xa,&ya,&xb,&yb,&xc,&yc);
Вычисляем вектора OA, OB, OC, AB, BC, CA.
OAx =
xa - xo; OAy = ya - yo;
OBx =
xb - xo; OBy = yb - yo;
OCx =
xc - xo; OCy = yc - yo;
ABx =
xb - xa; ABy = yb - ya;
BCx =
xc - xb; BCy = yc - yb;
CAx =
xa - xc; CAy = ya - yc;
Вычисляем косые произведения.
OAxAB
= OAx * ABy - OAy * ABx;
OBxBC
= OBx * BCy - OBy * BCx;
OCxCA
= OCx * CAy - OCy * CAx;
Если все повороты имеют один знак, то точка О лежит
внутри треугольника.
if
(((OAxAB <= 0) && (OBxBC <= 0) && (OCxCA <= 0)) ||
((OAxAB >= 0) &&
(OBxBC >= 0) && (OCxCA >=
0))) printf("1\n");
else
printf("0\n");
Реализация с помощью классов
#include <stdio.h>
class Point
{
private:
int x, y;
public:
Point(int x =
0, int y = 0) : x(x), y(y) {}
void
ReadPoint(void)
{
scanf("%d
%d",&x,&y);
}
int GetX(void)
{
return x;
}
int GetY(void)
{
return y;
}
};
class
Vector
{
private:
int dx, dy;
public:
Vector(int dx
= 0, int dy = 0) : dx(dx), dy(dy) {}
Vector(Point &a, Point &b)
{
dx = a.GetX() - b.GetX();
dy = a.GetY() - b.GetY();
}
int operator*(Vector &x)
{
return this->dx * x.dy - this->dy
* x.dx;
}
};
int main(void)
{
Point O;
O.ReadPoint();
Point A, B, C;
A.ReadPoint();
B.ReadPoint();
C.ReadPoint();
Vector OA(O,A); Vector AB(A,B);
Vector OB(O,B); Vector BC(B,C);
Vector OC(O,C); Vector CA(C,A);
if (((OA*AB
<= 0) && (OB*BC <= 0) && (OC*CA <= 0)) ||
((OA*AB >= 0) && (OB*BC >=
0) && (OC*CA >= 0)))
printf("1\n");
else printf("0\n");
return 0;
}