Алгоритм пересечения прямых и выпуклого многоугольгника
Difference between ru1 and ru2, changed 24 character(s)
Привет, **Codeforces**!↵
Заинтересовал вопрос о проверке пересекает ли прямая данный выпуклый многоугольник (прямых до 10^5, вершин в многоугольнике тоже до 10^5), все запросы в оффлайне. Долго искал в интернете, но ничего не нашёл, и в голову лезет только тупое решение за квадрат. Подскажите, пожалуйста, идею.

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 Первая редакция (опубликовано)