Сложная такая задача на процедуру

[Asya_inter]

Сложная такая задача на процедуру

449. Даны действительные числа x1, y1, x2, y2, ..., x6, y6. Точки с координатами (x1, y1), (x2, y2), (x3, y3) рассматриваются как вершины первого треугольника, точки с координатами (x4, y4), (x5, y5), (x6, y6) - второго треугольника. Выяснить, верно, ли что первый треугольник целиком содержится во втором, и если да, определить площадь области, принадлежащей внешнему треугольнику и не принадлежащей внутреннему. (Определить процедуру, позволяющую выяснить, лежат ли две точки в одной полуплоскости относительно заданной прямой, процедуру вычисления расстояния между двумя точками, а также процедуру вычисления площади треугольника по трем сторонам).

 

[Vladimir_S]

Определить процедуру, позволяющую выяснить, лежат ли две точки в одной полуплоскости относительно заданной прямой,

М-да, хотел бы я знать, как это сделать. Не, ну можно, конечно, через поворот системы координат, но это столько арифметики и писанины... Не знаете, нет ли попроще способа?

 

[Asya_inter]

Да, вот процедуры-то, я и не могу сделать. Преподаватель сказал, что нужно через уравнение прямой ax+by+c=0 , где a=y2-y1 b=x2-y2 и далее получаем с либо положительное, либо отрицательное, что дает нам понять лежат ли они в одной полуплоскости или нет. А как это реализовать не знаю.

 

[Vladimir_S]

Да, вот процедуры-то, я и не могу сделать. Преподаватель сказал, что нужно через уравнение прямой ax+by+c=0 , где a=y2-y1 b=x2-y2 и далее получаем с либо положительное, либо отрицательное, что дает нам понять лежат ли они в одной полуплоскости или нет. А как это реализовать не знаю.

Ага, ну понятно, что имеется в виду. Спасибо. Поразмыслю.

 

[Vladimir_S]

Вот, получите:

Var
 Xb1,Yb1,Xb2,Yb2,Xb3,Yb3,Xs1,Ys1,Xs2,Ys2,Xs3,Ys3:real;


Function One_Side(xl1,yl1,xl2,yl2,xp1,yp1,xp2,yp2:real):Boolean;

 Procedure Line(x1,y1,x2,y2:real; var al:real; var bl:real);
 begin
  al:=(y2-y1)/(x2-x1);
  bl:=-x1*(y2-y1)/(x2-x1)+y1;
 end;

 Function Y(x1,y1,x2,y2,x:real):real;
 var a,b:real;
 begin
  Line(x1,y1,x2,y2,a,b);
  Y:=a*x+b;
 end;

Begin
 if xl1=xl2 then
  One_Side:=(xp1-xl1)*(xp2-xl1)>=0
 else
 if yl1=yl2 then
  One_Side:=(yp1-yl1)*(yp2-yl1)>=0
 else
  One_Side:=(yp1-Y(xl1,yl1,xl2,yl2,xp1))*(yp2-Y(xl1,yl1,xl2,yl2,xp2))>=0;
End;

Function Square(x1,y1,x2,y2,x3,y3:real):real;
begin
 Square:=0.5*Abs((x1-x3)*(y2-y3)-(x2-x3)*(y1-y3));
end;

Begin
 Writeln('Small triangle:');
 Write('x1 = ');
 Readln(Xs1);
 Write('y1 = ');
 Readln(Ys1);
 Write('x2 = ');
 Readln(Xs2);
 Write('y2 = ');
 Readln(Ys2);
 Write('x3 = ');
 Readln(Xs3);
 Write('y3 = ');
 Readln(Ys3);
 Writeln;
 Writeln('Big triangle:');
 Write('x1 = ');
 Readln(Xb1);
 Write('y1 = ');
 Readln(Yb1);
 Write('x2 = ');
 Readln(Xb2);
 Write('y2 = ');
 Readln(Yb2);
 Write('x3 = ');
 Readln(Xb3);
 Write('y3 = ');
 Readln(Yb3);
 if One_Side(Xb1,Yb1,Xb2,Yb2,Xs1,Ys1,Xs2,Ys2) and
    One_Side(Xb1,Yb1,Xb2,Yb2,Xs1,Ys1,Xs3,Ys3) and
    One_Side(Xb1,Yb1,Xb2,Yb2,Xs2,Ys2,Xs3,Ys3) and
    One_Side(Xb1,Yb1,Xb3,Yb3,Xs1,Ys1,Xs2,Ys2) and
    One_Side(Xb1,Yb1,Xb3,Yb3,Xs1,Ys1,Xs3,Ys3) and
    One_Side(Xb1,Yb1,Xb3,Yb3,Xs2,Ys2,Xs3,Ys3) and
    One_Side(Xb2,Yb2,Xb3,Yb3,Xs1,Ys1,Xs2,Ys2) and
    One_Side(Xb2,Yb2,Xb3,Yb3,Xs1,Ys1,Xs3,Ys3) and
    One_Side(Xb2,Yb2,Xb3,Yb3,Xs2,Ys2,Xs3,Ys3)
   then
    Writeln('Yes! S = ',Square(Xb1,Yb1,Xb2,Yb2,Xb3,Yb3)-Square(Xs1,Ys1,Xs2,Ys2,Xs3,Ys3):0:3)
   else
    Writeln('No!');
 Readln
End.

 

[Asya_inter]

Vladimir_S, спасибо за решение. А вы бы могли хотя бы немного прокомментировать как и что здесь вы сделали, а то я ещё совсем плохо разбираюсь в pascal (я пытаюсь разобраться сама, но завтра уже сдавать, и думаю с комментариями я пойму быстрее)

 

[Vladimir_S]

Vladimir_S, спасибо за решение. А вы бы могли хотя бы немного прокомментировать как и что здесь вы сделали, а то я ещё совсем плохо разбираюсь в pascal (я пытаюсь разобраться сама, но завтра уже сдавать, и думаю с комментариями я пойму быстрее)

Хорошо, попробую.
Алгоритм проверки принадлежности вершин внутреннего треугольника к полуплоскости, лежащей по одну сторону прямой, проведенной через вершины внешнего треугольника, таков (булева функция One_Side):
1. Обозначим координаты двух вершин внешнего треугольника (xl1, yl1), (xl2, yl2).
2. Обозначим координаты двух вершин внутреннего треугольника (xp1, yp1), (xp2, yp2).
3. Через точки с координатами (xl1, yl1), (xl2, yl2) проводим прямую, уравнение которой задает внутренняя процедура Line. Формулу прямой, проходящей через две точки плоскости, Вы найдете в любом учебнике аналитической геометрии.
4. Определяем Y-координаты точек найденной прямой, соответствующих Х-координатам вершин внутреннего треугольника xp1 и xp2. Это делает внутренняя функция Y. Обозначим найденные точки Y1 и Y2.
5. Точки с координатами (xp1, yp1), (xp2, yp2) лежат по одну сторону прямой в том и только в том случае, когда знаки разностей (yp1-Y1) и (yp2-Y2) совпадают (либо одна из разностей нулевая). Совпадение знаков проверяем путём исследования знака произведения (yp1-Y1)*(yp2-Y2). Если это произведение неотрицательно, то да - точки лежат по одну сторону (или одна из них принадлежит прямой, что тоже годится).
6. Вертикальную и горизонтальную прямые рассматриваем отдельно.
7. Если координаты всех трёх пар точек внутреннего треугольника относительно всех трёх прямых, проведенных через пары вершин внешнего треугольника (итого - 9 комбинаций) удовлетворяют описанному свойству, то внутренний треугольник не вылезает за границы внешнего и можно считать площади. Если хоть в одной из этих комбинаций условие нарушается - то вылезает.
8. Формулу площади треугольника через координаты вершин можно найти в Интернете.
Всё!

 

[Asya_inter]

Vladimir_S, здравствуйте, а как программа выполняется, если значения b вдруг равны нулю? Как мы это устраняем? ( в том случае, если координаты стороны треугольника заданы по оси ох?

 

[Vladimir_S]

Vladimir_S, здравствуйте, а как программа выполняется, если значения b вдруг равны нулю? Как мы это устраняем? ( в том случае, если координаты стороны треугольника заданы по оси ох?

Прекрасно выполняется! Проверял еще при отладке.

Или Вы имеете в виду - при проведении прямой? Так ведь я же указал в п.6, что случаи прямых, параллельных координатным осям, рассмотрены отдельно: есть в подпрограмме соответствующее ветвление.

 

[Asya_inter]

Vladimir_S, спасибо вам большое) Да, я уже разобралась и всё поняла и задачу сдала)

 

[Vladimir_S]

Vladimir_S, спасибо вам большое) Да, я уже разобралась и всё поняла и задачу сдала)

Ура! Поздравляю.

 

[pusq]

А как реализовать данную программу на borland 3.1 c++? Та же задача, только в задании "Определить подпрограммы, необходимые для выяснения взаимного расположения треугольников и вычисления площади треугольника) Заранее спасибо!