Помощь - Поиск - Пользователи - Календарь
Полная версия: Применение процедур при решении задач
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
zoha
Даны координаты трех вершин треугольника ABC и даны координаты четвертой точки D. Определить, является ли эта точка внутренней точкой треугольника.

Есть какие-нить предположения? blink.gif blink.gif blink.gif
Unconnected
На олимпиадах подобные задачи часто решают следующим образом: "проводят" от точки D к вершинам треугольника три вектора и считают суммарную площадь трех образовавшихся треугольников. Если она больше площади исходного, то...
zoha
а исходник можно?
Unconnected
У меня нет исходника smile.gif
Попробуй сам начать. Знаешь, как найти длину вектора по координатам его концов?
DarkWishmaster
Цитата(Unconnected @ 21.05.2011 18:02) *

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


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

Изображение
Unconnected
Цитата
А на сколько точен это метод, ведь есть неточности с корнем и.т


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

Изображение
-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;
ето число Е?
zoha
Всем спасибо!!!
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.