Я пытаюсь решить проблему с SPOJ, это https://www.spoj.pl/problems/FSHEEP/
Нам нужно выяснить, находится ли точка внутри многоугольника. Как видим, это не выпуклый многоугольник (изображение из задачи).
Я пытался решить это за O (n * m) время с помощью алгоритма Ray Casting, описанного в Википедии или на любом другом сайте.
Но как решить это за O (n log m)? Другими словами, как проверить, находится ли точка в многоугольнике в логарифмическом времени?
Ваше здоровье
Так как это задача, напоминающая домашнее задание, я дам вам помощь в виде домашнего задания.
Практическое правило: всякий раз, когда вы видите log n, вы должны думать «что-то двоичное» (поиск, дерево и т. Д.). Когда вы видите n log n, вы должны подумать «сортировать». Вы будете удивлены, как часто это срабатывает. Можете ли вы отсортировать вершины и выполнить бинарный поиск по ним в рамках ограничений большого O?
ОБНОВИТЬ:
Я не хотел портить вам удовольствие: на самом деле вам даны вершины многоугольника в отсортированном порядке, поэтому важная сортировка была сделана за вас. Вам не нужно делать интервал в угловом пространстве, используйте индексы отсортированного массива вершин в качестве интервала.
Направьте свой луч от фермера к вершине. Если по часовой стрелке, двоичный поиск по часовой стрелке. Если он повернут против часовой стрелки, выполняется двоичный поиск в этом направлении. Две вершины и фермер образуют ограничивающий треугольник. Овца находится в ограничивающем треугольнике?
Безумный ленивый псевдокод:
if vertex[m] and vertex[0] trivially bound the sheep
l=m, r=0
else
l=0, r=m
while (r-l > 1)
middle = (r-l)/2
if vertex[l] and vertex[middle] bound sheep
r = middle
continue
else if vertex[middle] and vertex[r] bound sheep
l = middle
continue
else some_jerk_gave_you_a_sheep_on_a_ray
check vertex[l],vertex[r],farmer triangle
Двоичный поиск - O (log m). Проверка треугольника - O (1). Итерация по n овцам дает O (n) * O (log m) * O (1) = O (n log m).
