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

Revision ru2, by Hardes1, 2020-10-13 20:14:52

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

Tags геометрия

History

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