Алгоритм пересечения прямых и выпуклого многоугольгника

Правка ru1, от Hardes1, 2020-10-13 20:11:54

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

Теги геометрия

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский Hardes1 2020-10-13 20:14:52 24 Мелкая правка: 'е до 10^5). Долго ис' -> 'е до 10^5), все запросы в оффлайне. Долго ис'
ru1 Русский Hardes1 2020-10-13 20:11:54 343 Первая редакция (опубликовано)