143. Точка и треугольник

 

Принадлежит ли точка О треугольнику 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 y2x2 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;

}