Положение точки относительно выпуклого многоугольника

Чтобы определить, лежит ли точка внутри выпуклого многоугольника часто рекомендуют следующий подход:

1. Соединить эту точку отрезками с его вершинами.

2. Рассчитать площади получившихся треугольников.

3. Если сумма вычисленных площадей равна площади исходной фигуры (рис 3.9. а), то точка лежит внутри, если нет (рис 3.9. б) - снаружи.

Рис 3.9
Этот подход имеет несколько недостатков:

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

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

if (a*x[i+2]+b*y[i+2]+c)>0 then Rezalt:=’NO’;

на строку

if (a*x[0]+b*y[0]+c)>0 then Rezalt:=’NO’;

Так как мы не проверяем вершины многоугольника, нет необходимости вводить вторую фиктивную точку.

1. Напишите программу, которая определяет положение точки относительно многоугольника с использованиием первого подхода.

2. Напишите программу, которая определяет положение точки относительно многоугольника с использованиием предложенного подхода.

3. Решите задачу в случае, когда точка лежит на одной из сторон многоугольника. Изменится ли результат? Почему?