Применение процедур при решении задач Опции

[zoha]

Даны координаты трех вершин треугольника ABC и даны координаты четвертой точки D. Определить, является ли эта точка внутренней точкой треугольника.

Есть какие-нить предположения?

[Unconnected]

На олимпиадах подобные задачи часто решают следующим образом: "проводят" от точки D к вершинам треугольника три вектора и считают суммарную площадь трех образовавшихся треугольников. Если она больше площади исходного, то...

[zoha]

а исходник можно?

[Unconnected]

У меня нет исходника
Попробуй сам начать. Знаешь, как найти длину вектора по координатам его концов?

[DarkWishmaster]

На олимпиадах подобные задачи часто решают следующим образом: "проводят" от точки D к вершинам треугольника три вектора и считают суммарную площадь трех образовавшихся треугольников. Если она больше площади исходного, то...

А на сколько точен это метод, ведь есть неточности с корнем и.т
Поискал в гугле, вот что нашел:
Обычно задачи на принадлежность точки многоугольнику (произвольному) решаются так: проводится луч (обычно какого-нибудь простого вида, например налево или направо) из точки, принадлежность которой мы проверяем. считается количество пересечений со сторонами многоугольника, причем, если пересечение в нижней точке стороны, то она не учитывается, а в верхней - учитывается.
А как вообще это сделать? луч провести

Сообщение отредактировано: DarkWishmaster - 21.05.2011 18:54

[zoha]

Идея: Пусть есть треугольник ABC и точка D. Если Площадь ABC равна сумме
площадей треугольников ABD,BCD,CAD, то точка внутри треугольника.

Сообщение отредактировано: zoha - 21.05.2011 20:00

[zoha]

Примерная иллюстрация задачи, если это верно?

[Unconnected]

А на сколько точен это метод, ведь есть неточности с корнем и.т

Типа real вполне хватит. Да и везде подобные неточности..
А гугловый способ не очень понял. Если треугольник внизу и маленький, а точка с координатами (1000, 1000), куда его вести, спрашивается.. попасть ещё надо) Хотя, может, можно с уравнениями прямых-сторон поколдовать.

[zoha]

Примерная иллюстрация задачи, если это верно?



Сообщение отредактировано: zoha - 22.05.2011 11:51

[-TarasBer-]

> А на сколько точен это метод, ведь есть неточности с корнем и.т

Каким корнем?
Ты чё, площадь треугольника Героном берёшь?

На самом деле всё ещё проще - если площадки треугольников DAB, DBC, DCA одного знака, то внутри, если есть разного - то снаружи.

[zoha]

люди можно фрагмент процедуры?

[IUnknown]

Даны координаты трех вершин треугольника ABC и даны координаты четвертой точки D. Определить, является ли эта точка внутренней точкой треугольника.

Как узнать принадлежность

Процедуры, говоришь? Тут не процедуры, а функции надо использовать... Тебе в любом случае нужен результат: либо функция должна возвращать площадь треугольника, либо ответ True/False (внутри/снаружи, в смысле). Процедуры тут на фиг не нужны. Не надо пользоваться теми средствами, которые для решения задачи не подходят.

[-TarasBer-]

По ссылке формула

(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2;

Лучше её записать в виде

((b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x))/2;

Чтобы сразу было видно векторное произведение.
Ну и на одно умножение меньше.

[-TarasBer-]

> Тут не процедуры, а функции надо использовать...

А какая разница? Это же одно и то же.
Это только в синтаксисе Паскаля зачем-то сделали ненужное различие.

[zoha]

 program point_in_treug;
const _eps = 1E-7;
type TPoint = record
                 x,y : real;
              end;

var a,b,c,p : TPoint;
    s,s1,s2,s3 : real;

function sq_treug(a,b,c : TPoint) : real;
begin
   sq_treug := (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2;
end;

begin
   read(a.x,a.y);
   read(b.x,b.y);
   read(c.x,c.y);
   read(p.x,p.y);
   s := abs (sq_treug(a,b,c));
   s1 := abs (sq_treug(a,b,p));
   s2 := abs (sq_treug(a,p,c));
   s3 := abs (sq_treug(p,b,c));
   if abs (s - s1 - s2 - s3) < _eps then writeln('point is inside the triangle')
      else writeln('point is outside the triangle');
end.

поясните что здесь что?

[TarasBer]

Читай с самого начала: http://lib.mexmat.ru/books/14621

[zoha]

 _eps = 1E-7;

ето число Е?

[TarasBer]

http://ru.wikipedia.org/wiki/Экспоненциальная_запись

[zoha]

Всем спасибо!!!