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

Определите, лежит ли заданная точка внутри заданного треугольника.

Вход. Первые 3 строки содержат координаты вершин треугольника (в каждой строке по 2 целых числа). Четвертая строка содержит координаты точки, в таком же формате. Все числа – целые, по модулю не превосходящие 10000. Гарантируется, что вершины треугольника не лежат на одной прямой.

Выход. Вывести слово “In”, если точка лежит внутри треугольника, “On”, если точка лежит на границе треугольника (вершине или стороне), “Out” если точка лежит вне треугольника.

Пример входа	Пример выхода
-2 -2 3 1 0 1 0 0	In

РЕШЕНИЕ

геометрия

Анализ алгоритма

Точка O лежит внутри треугольника ABC тогда и только тогда, когда все три поворота OAB, OBC и OCA правые (треугольник ABC ориентирован по часовой стрелке) или левые (треугольник ABC ориентирован против часовой стрелки). То есть все выражения OA ´ AB, OB ´ BC, OC ´ CA имеют одинаковый знак (через ´ здесь обозначено псевдоскалярное произведение).

Пусть a(x₁, y₁) и b(x₂, y₂) – координаты векторов. Тогда

a ´ b = = x₁y₂ – x₂y₁

Точка O лежит на границе треугольника, если все выражения OA ´ AB, OB ´ BC, OC ´ CA либо неотрицательны, либо неположительны, но одно из них обязательно равно 0. Например, если O лежит на стороне BC, то OB ´ BC = 0.

Реализация алгоритма

Читаем координаты вершин треугольника A, B, C и точки О. Вычисляем требуемые векторные произведения.

scanf("%d %d %d %d %d %d %d %d",&xA,&yA,&xB,&yB,&xC,&yC,&xO,&yO);

// OA = (xA - xO,yA - yO)

// AB = (xB - xA,yB - yA)

OAxAB = (xA - xO)*(yB - yA) - (xB - xA)*(yA - yO);

// OB = (xB - xO,yB - yO)

// BC = (xC - xB,yC - yB)

OBxBC = (xB - xO)*(yC - yB) - (xC - xB)*(yB - yO);

// OC = (xC - xO,yC - yO)

// CA = (xA - xC,yA - yC)

OCxCA = (xC - xO)*(yA - yC) - (xA - xC)*(yC - yO);

Если все вычисленные произведения одного знака, точка О лежит внутри треугольника ABC. Если одно из произведений равно нулю, точка О лежит на границе треугольника. Иначе точка О находится вне треугольника.

if (((OAxAB > 0) && (OBxBC > 0) && (OCxCA > 0)) ||

((OAxAB < 0) && (OBxBC < 0) && (OCxCA < 0))) printf("In\n");

else

if (((OAxAB >= 0) && (OBxBC >= 0) && (OCxCA >= 0)) ||

((OAxAB <= 0) && (OBxBC <= 0) && (OCxCA <= 0))) printf("On\n");

else printf("Out\n");