Mif 17.15

Задача Mif17.15

Условие задачи

Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

Входные данные

В одной строке задано два числа – координаты точки latex[/latex].

Выходные данные

Вывести: «Принадлежит» или «Не принадлежит»(без кавычек).

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные	Выходные данные
1.	1.5 7	Не принадлежит
2.	3 4	Не принадлежит
3.	2 -3.6	Принадлежит
4.	5 0	Принадлежит
5.	0 1	Не принадлежит
6.	0 -4	Не принадлежит
7.	3 3	Принадлежит
8.	2 3	Принадлежит

Реализация

#include <iostream>
using namespace std;
 
int main () {
    double x, y, k, m, n;
    int x1=2, y1=5, x2=5, y2=0, x3=2, y3=-4; //координаты вершин треугольника
    cin >> x >> y; //координаты произвольной точки
    k= (x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y);
    m= (x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y);
    n= (x3 - x) * (y1 - y3) - (x1 - x3) * (y3 - y);
    cout << ((k>=0 && m>=0 && n>=0) || (k<=0 && m<=0 && n<=0)? "Принадлежит": "Не принадлежит");
    return 0;
}

#include <iostream>

using namespace std;

int main () {

double x, y, k, m, n;

int x1=2, y1=5, x2=5, y2=0, x3=2, y3=-4; //координаты вершин треугольника

cin >> x >> y; //координаты произвольной точки

k= (x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y);

m= (x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y);

n= (x3 - x) * (y1 - y3) - (x1 - x3) * (y3 - y);

cout << ((k>=0 && m>=0 && n>=0) || (k<=0 && m<=0 && n<=0)? "Принадлежит": "Не принадлежит");

return 0;

}

Алгоритм решения

Пусть на плоскости дан треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]C(x_3, y_3)[/latex]. А [latex]D(x, y)[/latex] — произвольная точка на координатной плоскости. Положим, [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] — векторы.

Для того, чтобы точка [latex]D(x, y)[/latex] принадлежала данному треугольнику, необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше или же меньше нуля.
Если векторы заданы своими координатами [latex]a(x_1, y_1), b(x_2, y_2)[/latex], то их косое произведение [latex][a,b]=x_1\cdot y_2 — x_2\cdot y_1[/latex]. Пользуясь данной формулой, запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]D(x, y)[/latex]: [latex]k=x_1y_2 — x_2y_1 — x_1y + xy_1 + x_2y — xy_2=(x_1 — x)\cdot (y_2 — y_1) — (x_2 — x_1)\cdot (y_1 — y)[/latex].
Далее запишем косое произведение векторов [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex]: [latex]m=x_2y_3 — x_3y_2 — x_2y + xy_2 + x_3y — xy_3=(x_2 -x)\cdot (y_ 3- y_2) — (x_3 — x_2)\cdot (y_2 — y)[/latex].
Запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] : [latex]n=x_1y_3 — x_3y_1 — x_1y + xy_1 + x_3y — xy_3=(x_3 — x)\cdot (y_1 — y_3) — (x_1 — x_3)\cdot (y_3 — y)[/latex].
Если [latex]k \leq 0 [/latex] и [latex]m \leq 0[/latex] и [latex]n \leq 0[/latex] или [latex]k \geq 0[/latex] и [latex]m \geq 0[/latex] и [latex]n \geq 0[/latex], то делаем вывод: точка принадлежит треугольнику.
Если ни одно из вышеуказанных условий не выполняется, то точка не принадлежит треугольнику.

Ознакомиться с теоретическим материалом можно здесь.

Для запроса на выполнение следует перейти по ссылке.

Related Images:

Похожее

3 thoughts on “Mif 17.15”

Я понимаю, что Вы имели в виду, но всё же:
— Вы пишите, что [latex]k= (x_1 — x)\cdot (y_2 — y_1) — (x_2 — x_1)\cdot (y_1 — y)[/latex] уравнение прямой, проходящей через указанные точки. Однако это так только если [latex]k= 0[/latex].
— Вы пишите «Если хотя бы одно из полученных значений равно нулю, то заданная точка лежит на стороне треугольника или же совпадает с одной из его вершин». Но сторона треугольника это отрезок. А Вы привели уравнение прямой. Т.е. бесконечно продолжающейся в обе стороны за пределами треугольника линии.
— Говорят, «лучшее враг хорошего». Пытаясь решить задачу лучше чем требуется, вы на самом деле решаете другую задачу. И в этой другой задаче делаете ошибку. Например, программа утверждает, что точка (300005;-500000) лежит на стороне треугольника или является его вершиной. А на самом деле из этой точки треугольник только в телескоп можно увидеть. Вывод: сначала нужно правильно решить поставленную задачу. Потом можно и пофантазировать.

А вообще Вы молодец — решение имеет большой потенциал. После того, как я удалил из него лишний условный оператор и добавил чтение координат вершин из входного потока, оно прошло для задачи №143 с e-olymp. Т.е. Вы на самом деле решили более сложную задачу — принадлежность точки любому треугольнику.
Когда исправите своё решение этой задачи, можете добавить ещё один код для задачи 143, а я засчитаю обе. Хорошо?

P.S. У нас на сайте уже обсуждалась подобная задача.

Кудымовская Вика says: 18/11/2015 at 00:39

Спасибо. Сейчас я решила задачу немного иначе. Для всех тестов проходит, сомневаюсь насчет метода решения, но другого пока не вижу.
Задачу 143 я размещу.