Задача №451. Принадлежность точки выпуклому многоугольнику
Ограничение по времени на все задачи – 1 секунда. Все входные данные – целые числа, по модулю не превышающие 10000. Все углы выводить в радианах. Все вещественные числа выводить с точностью до пятого знака после запятой. В случае неоднозначного ответа вывести любой верный.
Здесь можно применить один из стандартных алгоритмов проверки принадлежности точки произвольному многоугольнику, работающих за линейное время, однако проще воспользоваться тем, что многоугольник выпуклый, и решить подзадачу за O(logN). На то, что в данной конкретной задаче считывание данных происходит за линейное время, а запрос только один, не будем обращать внимание :)
Зафиксируем некоторую точку многоугольника (для понимания работы алгоритма можно выбрать самую нижнюю из самых левых) как начальную и перенесем в нее начало координат. Из того, что многоугольник выпуклый, следует, что все остальные точки отсортированы по полярному углу. Бинарным поиском найдем, между какими двумя вершиами многоугольника находится искомая точка. Если она совпадает по полярному углу с одной из вершин, то сравним расстояние от начала координат до точки и до вершины. В противном случае определим положение точки относительно отрезка, соединяющего две вершины, между которыми она лежит.
В бинарном поисве удобно переопределить оператор сравнения двух векторов: один вектор меньше другого, если их векторное произведение отрицатель но.