27 Вычислительная геометрия - задачи на многоугольники

(A) Площадь многоугольника

Задан многоугольник: сначала задано количество вершин многоугольника N, не превосходящее 100.000, затем N вершин многоугольника в порядке обхода. Выведите единственное число: площадь многоугольника.

     Ввод                         Вывод
     3                            0.5
     1 0
     0 1
     1 1

(B) Выпуклость многоугольника

Задан многоугольник, как в предыдущей задаче. Выведите YES, если многоугольник является выпуклым и NO в противном случае.

     Ввод                         Вывод
     3                            YES
     1 0
     0 1
     1 1

(C) Принадлежность точки многоугольнику

Первая строка входных данных содержит число N, 3≤N≤10⁵. Далее идет N точек – координаты вершин многоугольника. Затем идут координаты проверяемой точки. Программа должна вывести YES, если точка лежит внутри многоугольника или на его границе и NO в противном случае.

Координаты всех точек могут быть дробными числами!

     Ввод                         Вывод
     4                            NO
     0 0
     100 0
     1 1
     0 100
     2 2

(D) Принадлежность точки выпуклому многоугольнику

Первая строка входных данных содержит число N, 3≤N≤10⁵. Далее идет N точек – координаты вершин выпуклого многоугольника. Затем записано число K , 3≤N≤10⁵ – количество проверяемых точек. Затем в K строчках записаны координаты K проверяемых точек.

Для каждой проверяемой точки выведите YES, если точка лежит внутри многоугольника или на его границе и NO в противном случае.

Координаты всех точек могут быть дробными числами!

     Ввод                         Вывод
     3                             YES
     0 0                           NO
     2 0
     0 2
     2
     1 1
     2 2