Есть несколько алгоритмов проверки принадлежности точки произвольному многоугольнику. Один из самых простых, на мой взгляд, заключается в следующем.
Найдем сумму ориентированных углов, под которыми из данной точки видны все отрезки, соединяющие две последовательные точки данного многоугольника. Если она будет равна нулю (с точностью до eps), то точка находится строго снаружи. В противном случае точка лежит либо внутри, либо на границе многоугольника.
Как это считать? Здесь нам понадобится одна элементарная операция - нахождение угла между векторами. Пусть у нас есть точка O и две вершины A_i и A_i+1. Угол, под которым из O виден отрезок (A_i, A_i+1), равен углу между векторами (A_i - O) и (A_i+1 - O). Угол между векторами x и y можно посчитать функцией atan2([x, y], (x, y)), где [x, y] и (x, y) - соответственно векторное (косое) и скалярное произведения векторов.
Почему это работает? Вот интуитивное объяснение алгоритма. Пусть мы находимся в данной точке и хотим последовательно осмотреть весь многоугольник, вернувшись в начальную вершину. Если мы находимся снаружи, то, как бы не поворачивали взгляд, в конце он все равно вернется строго в исходное положение, не сделав лишних поворотов на 360 градусов, то есть суммарный угол поворота будет равен нулю. Если же мы находимся строго внутри, то для того, чтобы вернуться в исходную вершину, нам придется сделать полный оборот вокруг своей оси. В случае, когда мы находимся на границе, тоже должен произойти полный поворот вокруг своей оси, однако из-за способа вычисления значения угла в компьютере на практике получается промежуточное значение.
Входные данные
В первой строке вводятся три целых числа – N (3≤N≤100000) и координаты точки. Далее в N строках задается по паре целых чисел – координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.
Выходные данные
Выведите одну строку: “YES”, если заданная точка содержится в приведённом многоугольнике или на его границе, и “NO” в противном случае.