Здесь можно применить один из стандартных алгоритмов проверки принадлежности точки произвольному многоугольнику, работающих за линейное время, однако проще воспользоваться тем, что многоугольник выпуклый, и решить подзадачу за O(logN). На то, что в данной конкретной задаче считывание данных происходит за линейное время, а запрос только один, не будем обращать внимание :)
Зафиксируем некоторую точку многоугольника (для понимания работы алгоритма можно выбрать самую нижнюю из самых левых) как начальную и перенесем в нее начало координат. Из того, что многоугольник выпуклый, следует, что все остальные точки отсортированы по полярному углу. Бинарным поиском найдем, между какими двумя вершиами многоугольника находится искомая точка. Если она совпадает по полярному углу с одной из вершин, то сравним расстояние от начала координат до точки и до вершины. В противном случае определим положение точки относительно отрезка, соединяющего две вершины, между которыми она лежит.
В бинарном поисве удобно переопределить оператор сравнения двух векторов: один вектор меньше другого, если их векторное произведение отрицатель но.
Задан многоугольник и точка. Нужно определить, лежит ли точка внутри этого многоугольника. В этой задаче многоугольник выпуклый.
Решите задачу быстрым методом
Входные данные
Сначала вводится число N (3<=N<=100). Далее идут N пар вещественных чисел, задающих координаты вершин многоугольника. Последние два вещественных числа задают координаты точки.
Выходные данные
Выведите сообщение YES, если точка лежит внутри многоугольника, или NO в противном случае. Гарантируется, что точка не лежит на границе многоугольника.