Задачи
Точка в многоугольнике
Точка в многоугольнике
Как известно, простой многоугольник - это фигура, состоящая из непересекающихся отрезков ("сторон"), соединённых попарно с образованием замкнутого пути. По заданному простому многоугольнику и точке требуется определить, лежит ли эта точка внутри или на границе этого многоугольника или вне его.
Входные данные
В первой строке заданы три числа: n (3 ≤ n ≤ 10^5) и координаты точки. Далее в n строках заданы по паре чисел - координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.
Выходные данные
Вывести строку "YES", если заданная точка содержится в приведённом многоугольнике или на его границе, и "NO" в противном случае.
Пример
Входные данные #1
3 0 0 1 0 0 1 1 1
Выходные данные #1
NO
Входные данные #2
4 3 2 0 0 1 5 5 5 6 0
Выходные данные #2
YES