А54

by

4

Задача:

Даны действительные числа [latex]x_{1}[/latex], [latex]x_{2}[/latex], [latex]x_{3}[/latex], [latex]y_{1}[/latex],[latex]y_{2}[/latex], [latex]y_{3}[/latex].

Принадлежит ли начало координат треугольнику с вершинами [latex]\left( x_{1} ; y_{1} \right) [/latex], [latex]\left( x_{2} ; y_{2} \right) [/latex], [latex]\left( x_{3} ; y_{3} \right) [/latex]?

 
  [latex] x_{1} [/latex]   [latex] y_{1} [/latex]   [latex] x_{2} [/latex] [latex] y_{2} [/latex]   [latex] x_{3} [/latex]   [latex] y_{3} [/latex] Предполагаемый результат Вывод
 -400  0  240  1  210  1  Не принадлежит  Тест пройден
 -400  0  240  1  210  -1  Принадлежит  Тест пройден
 0  0  240  -1  2100  -1  Принадлежит  Тест пройден
 -2  -2  5  -2  1  10  Принадлежит  Тест пройден
 3  0  40  0  15  10  Не принадлежит  Тест пройден
 -24  -2  29  -2  29  10  Принадлежит Тест пройден
 -12  -5  14  -5  7  -5  Жаль вас расстраивать… Тест пройден

 

 

Описание:

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

 

Краткий алгоритм:

  1. Объявление переменных, обозначающих координаты вершин  треугольника.
  2. Ввод координат вершин треугольника.
  3. Небольшая проверка  правильности ввода.
  4. С помощью общего уравнения прямой [latex]\frac{y-y_{1}}{y_{2}-y_{1}}=\frac{x-x_{1}}{x_{2}-x_{1}}[/latex], приведенного в вид :[latex]\left(y_{2}-y_{1} \right) \left(x-x_{1}\right)-\left(y-y_{1} \right) \left(x_{2}-x_{1}\right)=0[/latex],- определяем расположение вершин треугольника относительно противоположных им сторон (название переменной показывает, какую вершину проверяют), а также начала координат относительно тех же сторон, после чего следует умножение соответствующих величин. В случае, если произведение больше, либо равно нулю во всех трех случаях, можно сделать вывод о том, что точка находится внутри треугольника.
  5. Вывод вердикта и окончание работы.

Ссылка на Ideone.

Related Images:

4 thoughts on “А54”

  1. Ваш метод с суммой площадей не очень подходит для компьютерной реализации. Вам приходится сравнивать действительные числа на равенство, а этого лучше избегать. Мы на лекции говорили о причинах.

    А какой же алгоритм лучше?
    Рассмотрим прямую AB. Если уравнение этой прямой подставить координаты точки не лежащей на ней, то уравнение превратится в неравенство. Знак неравенства будет отличаться в зависимости от того в какой полуплоскости лежит точка. Значит, если подставить координаты точки С и начала координат и получить одинаковый знак, то обе точки лежат по одну сторону от АВ. Проделав тоже самое с BC и CD мы сможем убедиться, что точке лежит внутри треугольника. Кстати, уравнение прямой лучше записать в виде (x — x1)(y2 -y1) — (y — y1)(x2 — x1) = 0. Если в эту формулу по очереди подставить координаты пары точек и перемножить полученные результаты, то значение >=0 будет означать, что точки лежат с одной стороны прямой. Вместо умножения возможно лучше сделать сложное логическое выражение с учётом теоретической возможности попадания точно в ноль, что подходит и для положительного и для отрицательного второго значения.
    Кроме всего прочего программа будет работать значительно быстрее — меньше вычислений и нет трудоёмких функций вроде вычисления корня.

    Если не переделывать всё, то нужно учесть такие замечания:

    1. Суть алгоритма вы описать забыли. Как я понял Вы утверждаете, что если площадь треугольника равна сумме площадей трёх треугольников, образованных точками A, B, C и началом координат, то начало координат лежит внутри. Совершенно справедливо. Только это нужно показать. Т.е. хотя бы упомянуть, что сумма площадей станет больше исходной если точка выйдет за границы треугольника. Но явно не хватает рисунка с обозначением всех ваших площадей, точек и длин. Если сделаете рисунок (закодировав текстом, а не нарисовав в редакторе!) в формате векторной графики SVG, то сможете получить дополнительные максимум 10 баллов.
    2. «ошибка измерения» — это когда Вы линеечку прикладываете и смотрите на деления. Здесь же возникает ошибка округления при вычислениях,
    3. нет ссылки на код в IDEone,
    4. переменные x и y объявлены, но нигде не используются поскольку непосредственно подставлены в формулы вычисления длин сторон составляющих треугольников.
    5. использование относительной погрешности действительно целесообразною Вполне достаточно просто разделить S1+S2+S3 на S и потребовать, чтобы эта величина отличалась от 1 не более чем, например, на 0.0001. В программе Вы используете совсем другую формулу S1+S2+S3 — S <= fabs(1-sqrt(S1*S1+S2*S2+S3*S3)/S). Я записал Ваше условие чуть иначе, чтобы было видно, что слева абсолютное отклонение, а справа относительное. Слева могут быть отрицательные значения, а справа - нет. Нас это устраивает поскольку суммарная площадь не будет меньше площади треугольника. Но нужно либо обосновать Вашу оценку абсолютной погрешности, либо дать ссылку на источник.
    6. Метки, это ключевые слова. Нельзя записывать сюда целое предложение. Обязательно исправьте.

  3. Прочитав замечания, понял, что правильнее ( да и просто легче) переделать решение, с помощью метода, предложенного Вами.
    P.S. Уже прочитал.

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