Mif 17.15

Задача Mif17.15

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

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

Viktoriya_Kudymovskaya (1)

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

В одной строке задано два числа – координаты точки [latex](x,y)[/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 Принадлежит

Реализация

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

Пусть на плоскости дан треугольник [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] — векторы.

  1. Для того, чтобы точка [latex]D(x, y)[/latex] принадлежала данному треугольнику, необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше или же меньше нуля.
  2. Если векторы заданы своими координатами [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].
  3. Далее запишем косое произведение векторов [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].
  4. Запишем косое произведение векторов [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].
  5. Если [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], то делаем вывод: точка принадлежит треугольнику.
  6. Если ни одно из вышеуказанных условий не выполняется, то точка не принадлежит треугольнику.

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

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

3 thoughts on “Mif 17.15

  1. Я понимаю, что Вы имели в виду, но всё же:
    — Вы пишите, что [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. У нас на сайте уже обсуждалась подобная задача.

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

Добавить комментарий