Блог пользователя Hardes1

Алгоритм пересечения прямых и выпуклого многоугольгника
Автор Hardes1, история, 4 года назад, По-русски

Привет, Codeforces! Заинтересовал вопрос о проверке пересекает ли прямая данный выпуклый многоугольник (прямых до 10^5, вершин в многоугольнике тоже до 10^5), все запросы в оффлайне. Долго искал в интернете, но ничего не нашёл, и в голову лезет только тупое решение за квадрат. Подскажите, пожалуйста, идею.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Hardes1 (предыдущая версия, новая версия, сравнить).

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Сначала нужно поделить выпуклый многоугольник на верхнюю "оболочку" и нижнюю "оболочку". Теперь от каждой прямой до любой из двух этих оболочек мы можем найти минимальное/максимальное расстояние тернарным поиском. При этом если точка находится ниже прямой, расстояние считается отрицательным. Искать расстояние нужно на массиве вершин, пытаясь найти минимальное/максимальное расстояние до вершины. При этом непонятно будет ли расстояние сначала увеличиваться, потом уменьшатся или наоборот, сначала уменьшатся, а потом увеличиваться, поэтому на каждую оболочку нужно применить оба тернарных поиска. В итоге если максимальное расстояние больше нуля а минимальное меньше, значит прямая где то пересекла "оболочку". Если одно из расстояний равно нулю, пересечение также есть.

→ Ответить